Question
Digit‐Sum Target Subsets
You’re given an array nums of size n, and an integer target. The digit‐sum of a number X is defined as the sum of its decimal digits (e.g. digit‐sum (305) = 3 + 0 + 5 = 8).
Count the number of subsets of nums such that the sum of the digit-sums of the elements in that subset is exactly equal to target.
Because the answer can be large, you may return it modulo 109 + 7.
Note: A subset is any selection of elements from the array, where each element is either included or excluded — regardless of order.
The empty subset is allowed and its total digit-sum is defined to be 0.
Input
The first line of input contains two space-separated integers, n and target.
The second line contains n space-separated integers, representing the elements of array nums
The second line contains n space-separated integers, representing the elements of array nums
Output
Print a single integer — the number of subsets whose total digit‑sum equals target, modulo 10 9 + 7
Example
Input
1 3
12
Output
1
Explanation
Since the array contains only one element, and its digit sum (e.g., 12 → 1 + 2 = 3) equals the target, there is exactly one valid subset.
Input
3 0
0 0 0
Output
8
1 3
12
Output
1
Explanation
Since the array contains only one element, and its digit sum (e.g., 12 → 1 + 2 = 3) equals the target, there is exactly one valid subset.
Input
3 0
0 0 0
Output
8