> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/n-digit-numbers-with-digit-sum-s.md).

# N digit numbers with digit sum S

Find out the number of `N` digit numbers, whose digits on being added equals to a given number `S`. 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`

`N = 2, S = 4`

\
Valid numbers are `{22, 31, 13, 40}`\
Hence output `4`.

```java
public class Solution {

    private long MOD = 1000000007L;

    public int solve(int n, int sum) {
        long[][] dp = new long[n + 1][sum + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= sum; j++) {
                dp[i][j] = -1;
            }
        }
        long count = 0;
        // For first digit we can only take 1->9
        for (int i = 1; i <= 9; i++) {
            if (sum - i >= 0) {
                count += recursion(n - 1, sum - i, dp) % MOD;
            }
        }
        return (int) (count % MOD);
    }

    private long recursion(int n, int sum, long[][] dp) {
        if (n == 0) {
            return sum == 0 ? 1 : 0;
        }
        if (dp[n][sum] != -1)
            return dp[n][sum];
        long count = 0;
        for (int i = 0; i <= 9; i++) {
            if (sum - i >= 0) {
                count += recursion(n - 1, sum - i, dp);
            }
        }
        dp[n][sum] = count % MOD;
        return dp[n][sum];
    }
}
```