<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>

#include <vector>
#include <unordered_map>
#include <utility>

using namespace std;

// Custom hash function for pair<int, int> to use in unordered_map
struct hash_pair {
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1,T2>& p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ h2; // Combine the hash values
    }
};

class Solution {
public:
    // Modulo constant
    const int MOD = 1e9 + 7;

    // Memoization map
    unordered_map<pair<int, int>, int, hash_pair> memo;

    // Recursive function with memoization
    int dp(int n, int sum, int k, int target) {
        // If sum exceeds target, return 0
        if (sum > target) return 0;
        // Base case: no dice left
        if (n == 0) return (sum == target) ? 1 : 0;

        // Check memoization table
        if (memo.find({n, sum}) != memo.end()) {
            return memo[{n, sum}];
        }

        // Calculate the number of ways
        int result = 0;
        for (int face = 1; face <= k; ++face) {
            result = (result + dp(n - 1, sum + face, k, target)) % MOD;
        }

        // Store result in memoization table
        memo[{n, sum}] = result;
        return result;
    }

    int numRollsToTarget(int n, int k, int target) {
        memo.clear(); // Clear the memoization map
        return dp(n, 0, k, target);
    }
};

17360