N digit number.txt

N digit numbers
Problem Description

Find out the number of A digit positive numbers, whose digits on being added equals to a given number B.

Note that a valid number starts from digits 1-9 except the number 0 itself. i.e. leading zeroes are not allowed.

Since the answer can be large, output answer modulo 1000000007



Problem Constraints
1 <= A <= 1000

1 <= B <= 10000



Input Format
First argument is the integer A

Second argument is the integer B



Output Format
Return a single integer, the answer to the problem



Example Input
Input 1:

 A = 2
 B = 4
Input 2:

 A = 1
 B = 3


Example Output
Output 1:

 4
Output 2:

 1


Example Explanation
Explanation 1:

 Valid numbers are {22, 31, 13, 40}
 Hence output 4.
Explanation 2:

 Only valid number is 


int dp[10001][1001];
long long int M=1e9+7;
long long int soln(int index,int A,int B){
    if(index==A and B==0)
    return 1;
    if(index==A or B<0)
    return 0;
    if(dp[index][B]!=-1)
    return dp[index][B];
    int start= index==1?1:0;
    long int ways=0;
    for(int i=start;i<=9;i++){
        ways =(ways+soln(index+1,A,B-i))%M;
    }
    return dp[index][B]=ways%M;
}
int Solution::solve(int A, int B) {
    memset(dp,-1,sizeof(dp));
    return soln(0,A,B);
}