Given two integers ‘n’ and ‘sum’, find the count of all n digit numbers whose sum of digits is ‘sum’. Leading 0’s are not counted as digits.
Example 1:
Input: n = 2, sum = 2
Output: 2
Explaination:
The 2 digit numbers are 11 and 20.
Example 2:
Input: n = 1, sum = 10
Output: -1
Explaination:
We cannot get sum as 10 from a single digit.
Your Task:
You do not need to read input or print anything. Your task is to complete the function countWays() which takes the value n and sum as input parameters and returns the number of possible ways modulo 10^{9}+7. If there is no possible way then it returns -1.
Expected Time Complexity: O(nsum)
Expected Auxiliary Space: O(nsum)
Constraints:
1 ≤ n ≤ 10^{2}
1 ≤ sum ≤ 10^{3}

见题面

见题面