Google OA 2023 - Finding Arrays

Given an array S of N elements. We need to find the count of distinct arrays A of N elements that exists such that:

• A[i]< A[i+1] for all 1 ≤ i< N.

• Sum of digits of A[i] is equal to S[i] for all 1 ≤ i ≤N.

• 1≤ A[i] ≤ 10^3

An array A is said to be different from array B if there exists an index i such that for all i from 1 to N.

Since the count can be very large. Output the answer modulo 10^9 + 7.

Note: Consider 1-based indexing.

Input format

First line contains an integer T, denoting the number of test cases
For each test case:
First line contains an Integer N.
Second line contains N space-separated integers, denoting array S.

Output format

For Each Test case print the required answer in a new line

Constraints

1 <T≤5
1 ≤ N ≤ 100
1 ≤ S[i] ≤ 30

Sample Input

1
2
2 1

Sample Output

9

Explanation: Given arrays are possible - [2,10], [2,100], [2,1000], [11,100], [11,1000], [20,100], [20,1000], [101,1000], [110,1000]

Sample Input
4
3
10 15 16
6
3 6 10 14 12 17
10
3 9 9 3 11 7 14 15 11 17
9
2 7 3 5 9 13 9 14 11

Sample Output
101776
142727553
303300404
19829619