<p>You have <code>n</code> dice, and each dice has <code>k</code> faces numbered from <code>1</code> to <code>k</code>.</p>

<p>Given three integers <code>n</code>, <code>k</code>, and <code>target</code>, return <em>the number of possible ways (out of the </em><code>k<sup>n</sup></code><em> total ways) </em><em>to roll the dice, so the sum of the face-up numbers equals </em><code>target</code>. Since the answer may be too large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 1, k = 6, target = 3
<strong>Output:</strong> 1
<strong>Explanation:</strong> You throw one die with 6 faces.
There is only one way to get a sum of 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2, k = 6, target = 7
<strong>Output:</strong> 6
<strong>Explanation:</strong> You throw two dice, each with 6 faces.
There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 30, k = 30, target = 500
<strong>Output:</strong> 222616187
<strong>Explanation:</strong> The answer must be returned modulo 10<sup>9</sup> + 7.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n, k &lt;= 30</code></li>
	<li><code>1 &lt;= target &lt;= 1000</code></li>
</ul>

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        // const long long M = 1e9 + 7;
        // long long dp[n+1][target+1];

        // for(int i=0; i<=n; i++){
        //     for(int j=0; j<=target; j++){
        //         dp[i][j] = -1;
        //     }
        // }

        // // row 1
        // for(long long  j=1; j<=target; j++){
        //     if(j<=k) dp[1][j] = 1;
        //     else dp[1][j] = 0;
        // }

        // for(long long i=1; i<=n; i++){
        //     for(long long j=1; j<=target; j++){
        //         cout << dp[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        // cout << "*********************" << endl;

        // for(long long  i=2; i<=n; i++){
        //     long long  minus = 1;
        //     for(long long  j=1; j<=target; j++){
        //         if(i>j) dp[i][j] = 0;
        //         else if(i == j) dp[i][j] = 1;
        //         else{
        //             if(k+i>j){
        //                 cout << "dp[i][j-1] = " << dp[i][j-1] << " dp[i-1][j-1] = " << dp[i-1][j-1] << endl;
        //                 dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
        //             }
        //             else{
        //                 long long is_neg = dp[i][j-1] + dp[i-1][j-1] - minus;
        //                 if(i != 2) minus++;
        //                 if(is_neg < 0) is_neg = 0;
        //                 dp[i][j] = is_neg;
        //             }
        //         }
        //     }

        //     for(long long i=1; i<=n; i++){
        //         for(long long j=1; j<=target; j++){
        //             cout << dp[i][j] << " ";
        //         }
        //         cout << endl;
        //     }
        //     cout << "*********************" << endl;
        // }

        // return dp[n][target]%M;

        // const int M = 1e9 + 7;
        // // cout << M;
        // int dp[target+1];
        // for(int i=0; i<=target; i++) dp[i] = 0;
        // dp[0] = 1;

        // for(int i=0; i<=target; i++) cout << dp[i] << " ";
        // cout << endl;
        // cout << endl;

        // for(int i=0; i<n; i++){
        //     int next_dp[target+1];
        //     for(int j=0; j<=target; j++) next_dp[j] = 0;

        //     for(int val=1; val<=k; val++){
        //         for(int total=k; total<=target; total++){
        //             next_dp[total] = (next_dp[total] + dp[total-val]) % M; 
        //         }
        //     }

        //     for(int i=0; i<=target; i++) cout << next_dp[i] << " ";
        //     cout << endl;

        //     for(int j=0; j<=target; j++) dp[j] = next_dp[j];

        //     for(int i=0; i<=target; i++) cout << dp[i] << " ";
        //     cout << endl;
            
        //     cout << endl;
        // }

        // return dp[target];

        const int M = 1e9 + 7;
        int prev_dp[target + 1];

        prev_dp[0] = 1;
        for(int i=1; i<=target; i++) prev_dp[i] = 0;

        for(int i=1; i<=n; i++){
            int curr_dp[target + 1];
            for(int j=0; j<=target; j++) curr_dp[j] = 0;

            for(int j=1; j<=k; j++){
                for(int l=j; l<=target; l++){
                    curr_dp[l] = (curr_dp[l] + prev_dp[l-j]) % M;
                }
            }

            for(int j=0; j<=target; j++) prev_dp[j] = curr_dp[j];
        }

        return prev_dp[target];
    }
};
7280