here is my code:

Code: Select all

```
#include <iostream>
using namespace std;
int main()
{
long long dp[11][101][10];
memset(dp, 0, sizeof dp);
for (int i = 0; i < 11; i++)
for (int j = 0; j < 10; j++)
if (j)
dp[i][1][j] = 1;
else
dp[i][1][j] = 0;
for (int base = 2; base <= 10; base++)
for (int len = 2; len <= 100; len++)
for (int lastd = 0; lastd < base; lastd++)
{
if (lastd == 0)
dp[base][len][lastd] = dp[base][len-1][lastd+1];
if (lastd == base-1)
dp[base][len][lastd] = dp[base][len-1][lastd-1];
if (lastd > 0 && lastd < base-1)
dp[base][len][lastd] = (dp[base][len-1][lastd-1] + dp[base][len-1][lastd+1]) % 1000000007;
}
int N, M, t;
cin >> t;
while (t--)
{
cin >> N >> M;
long long ans = 0;
for (int l = 1; l < M; l++)
for (int ld = 0; ld < N; ld++)
ans = (ans + dp[N][l][ld]) % 1000000007;
cout << ans << endl;
}
}
```