Google OA-5 2023

Problem Description

You are given an array of S containing N elements. Your goal is to determine the count of distinct arrays A of N elements that satisfy the following conditions:

• A[i] < A[i+1] for all 1 ≤ i < N.
• The sum of the digits of A[i] must equal S[i] for all 1 ≤ i ≤ N.
• Each element must satisfy 1 ≤ A[i] ≤ 10^3.

Two arrays A and B are considered different if there exists at least one index i such that A[i] ≠ B[i] for any i from 1 to N.

Since the resulting count can be very large, output the answer modulo 10^9 + 7.

Note: Use 1-based indexing.

Input format

The first line contains an integer T, denoting the number of test cases
For each test case:
The first line contains an Integer N.
The 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:
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 2:
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