<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 {
    static const int mod=1000000007;
    // int helper(int d,int s,int l,vector<vector<int>>&dp)
    // {
    //     if(s==0)
    //     {
    //         if(d==0)
    //         return 1;
    //         return 0;
    //     }
    //     if(d>=l)
    //     return 0;
    //     if(dp[d][s]!=-1)
    //     return dp[d][s];
    //     int ans=0;
    //     //stay
    //     if(s-1>=d)
    //     ans=(ans+helper(d,s-1,l,dp))%mod;
    //     //left
    //     if(d>0&&s-1>=d-1)
    //     ans=(ans+helper(d-1,s-1,l,dp))%mod;
    //     //right
    //     if(s-1>=d+1&&d<l)
    //     ans=(ans+helper(d+1,s-1,l,dp))%mod;
    //     return dp[d][s]=ans%mod;
    // }
public:
    int numWays(int s, int l) {
        vector<vector<long long>>dp(min(l,s)+2,vector<long long>(s+1,0));
        dp[0][0]=1;
        
            for(int i=1;i<=s;i++)
            {for(int d=0;d<min(l,s);d++)
        {
                int ans=0;
                //stay
                if(i-1>=d)
                ans=(ans+dp[d][i-1])%mod;
                //left
                if(d>0&&i-1>=d-1)
                ans=(ans+dp[d-1][i-1])%mod;
                //right
                if(i-1>=d+1&&d<l)
                ans=(ans+dp[d+1][i-1])%mod;
                 dp[d][i]=ans%mod;
            }
        }
        return dp[0][s];
    }
};
21026