<p>You have a pointer at index <code>0</code> in an array of size <code>arrLen</code>. At each step, you can move 1 position to the left, 1 position to the right in the array, or stay in the same place (The pointer should not be placed outside the array at any time).</p>

<p>Given two integers <code>steps</code> and <code>arrLen</code>, return the number of ways such that your pointer is still at index <code>0</code> after <strong>exactly</strong> <code>steps</code> steps. 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> steps = 3, arrLen = 2
<strong>Output:</strong> 4
<strong>Explanation: </strong>There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay
</pre>

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

<pre>
<strong>Input:</strong> steps = 2, arrLen = 4
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay
</pre>

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

<pre>
<strong>Input:</strong> steps = 4, arrLen = 2
<strong>Output:</strong> 8
</pre>

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

<ul>
	<li><code>1 &lt;= steps &lt;= 500</code></li>
	<li><code>1 &lt;= arrLen &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution {
public:

    struct pair_hash
    {
        template <typename T, typename U>
        std::size_t operator () (const std::pair<T, U> &x) const
        {
            return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
        }
    };

    int numWays(int steps, int arrLen) 
    {
        int MOD = 1000000007;
        std::unordered_map<std::pair<int, int>, int, pair_hash> ways;
        // <int, int> -- <steps, index>

        ways[{1,0}] = 1;
        ways[{1,1}] = 1;

        for (int step = 2; step <= steps; ++step)
        {
            int max_ind = std::min(step, arrLen - 1);
            for (int ind = 0; ind <= max_ind; ++ind)
            {
                int w = ways[{step - 1, ind}];

                if (ind > 0)
                    w = (w + ways[{step - 1, ind - 1}]) % MOD;

                if (ind < max_ind)
                    w = (w + ways[{step - 1, ind + 1}]) % MOD;

                ways[{step, ind}] = w;
            }
        }

        return ways[{steps, 0}];
    }
};




// class Solution {
// public:
//     int MOD = 1000000007;

//     int numLR(int steps, int arrLen)
//     {
//         int l = steps / 2;
//         return 0;
//     }

//     int fact(int n)
//     {
//         int r = 1;
//         for (int i = 1; i <= n; ++i)
//         {
//             r = r * i;
//         }
//         return r;
//     }

//     int numZ(int zeroes, int len)
//     {
//         // 2 zeroes, <><> len = 4

//         len = len + zeroes;

//         int r = 1;
//         for (int i = 0; i < zeroes; ++i)
//         {
//             r = r * (len - i) % MOD;
//         }

//         r = r / fact(zeroes);

//         return r;
//     }


//     int f(int steps, int i, int open, string c)
//     {
//         //cout << "s(" << steps << "," << i << "," << open << ")" << endl;

//         int r = 0;
//         if (i == steps - 1)
//         {
//             if (open == 1)
//             {
//                 c += ")";
//                 cout << c << endl;
//                 return 1;
//             }
//             else
//             {
//                 return 0;
//             }
//         }

//         if (open > 0)
//             r += f(steps, i + 1, open - 1, c + ")");
        
//         r += f(steps, i + 1, open + 1, c + "(");

//         return r;
//     }

//     int numWays(int steps, int arrLen) 
//     {
//         f(10, 0, 0, "");

//         // cout << "f(2): " << f(2, 0, 0) << endl;
//         // cout << "f(4): " << f(4, 0, 0) << endl;
//         // cout << "f(6): " << f(6, 0, 0) << endl;
//         //cout << "f(8): " << f(8, 0, 0) << endl;
//         //cout << "f(10): " << f(10, 0, 0, "") << endl;
//         // cout << "f(12): " << f(12, 0, 0) << endl;

//         //f(4, 0, 0);
//         //cout << "f(8): " << f(8, 0, 0) << endl;

//         return 0;
//     }
// };
62195