C. Planar Reflections-CodeCraft-21 and Codeforces Round #711 (Div. 2)

Problem - C - Codeforces

C. Planar Reflections

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Gaurang has grown up in a mystical universe. He is faced by nn consecutive 2D planes. He shoots a particle of decay age kk at the planes.

A particle can pass through a plane directly, however, every plane produces an identical copy of the particle going in the opposite direction with a decay age k−1k−1. If a particle has decay age equal to 11, it will NOT produce a copy.

For example, if there are two planes and a particle is shot with decay age 33 (towards the right), the process is as follows: (here, D(x)D(x) refers to a single particle with decay age xx)

1. the first plane produces a D(2)D(2) to the left and lets D(3)D(3) continue on to the right;
2. the second plane produces a D(2)D(2) to the left and lets D(3)D(3) continue on to the right;
3. the first plane lets D(2)D(2) continue on to the left and produces a D(1)D(1) to the right;
4. the second plane lets D(1)D(1) continue on to the right (D(1)D(1) cannot produce any copies).

In total, the final multiset SS of particles is {D(3),D(2),D(2),D(1)}{D(3),D(2),D(2),D(1)}. (See notes for visual explanation of this test case.)

Gaurang is unable to cope up with the complexity of this situation when the number of planes is too large. Help Gaurang find the size of the multiset SS, given nn and kk.

Since the size of the multiset can be very large, you have to output it modulo 109+7109+7.

Note: Particles can go back and forth between the planes without colliding with each other.

Input

The first line of the input contains the number of test cases tt (1≤t≤1001≤t≤100). Then, tt lines follow, each containing two integers nn and kk (1≤n,k≤10001≤n,k≤1000).

Additionally, the sum of nn over all test cases will not exceed 10001000, and the sum of kk over all test cases will not exceed 10001000. All test cases in one test are different.

Output

Output tt integers. The ii-th of them should be equal to the answer to the ii-th test case.

Examples

input

Copy

4
2 3
2 2
3 1
1 3

output

Copy

4
3
1
2

input

Copy

3
1 1
1 500
500 250

output

Copy

1
2
257950823

Note

Let us explain the first example with four test cases.

Test case 1: (n=2n=2, k=3k=3) is already explained in the problem statement.

See the below figure of this simulation. Each straight line with a different color represents the path of a different particle. As you can see, there are four distinct particles in the multiset. Note that the vertical spacing between reflected particles is for visual clarity only (as mentioned before, no two distinct particles collide with each other)

Test case 2: (n=2n=2, k=2k=2) is explained as follows:

1. the first plane produces a D(1)D(1) to the left and lets D(2)D(2) continue on to the right;
2. the second plane produces a D(1)D(1) to the left and lets D(2)D(2) continue on to the right;
3. the first plane lets D(1)D(1) continue on to the left (D(1)D(1) cannot produce any copies).

Total size of multiset obtained {D(1),D(1),D(2)}{D(1),D(1),D(2)} is equal to three.

Test case 3: (n=3n=3, k=1k=1), there are three planes, but decay age is only one. So no new copies are produced while the one particle passes through the planes. Hence, the answer is one.

Test case 4: (n=1n=1, k=3k=3) there is only one plane. The particle produces a new copy to the left. The multiset {D(2),D(3)}{D(2),D(3)} is of size two.

==================================================================================================================================================

典型的DFS，但是我不知道为什么本地运行爆了时间但是cf交上去100ms就过了....

用到一个小剪枝，设置dp[nowk][nowpos][fang]数组，代表能量位置和方向，访问到了就可以返回值。

# include<iostream>
# include<cstring>
using namespace std;
 
# define mod 1000000007
 
typedef long long int ll;
 
ll dp[1010][1010][2];
 
ll n, k;
 
ll dfs(int nowk,int nowpos,int fang)
{
 
 
 
    if(nowk==1||nowpos==0||nowpos>n)
    {
        return  1;
    }
 
    if(dp[nowk][nowpos][fang]!=-1)
    {
        return dp[nowk][nowpos][fang]%mod;
 
    }
 
    ll ans=0;
 
    if(fang==1)  //向右
    {
       ans=(ans+dfs(nowk,nowpos+1,fang))%mod;
 
       ans=(ans+dfs(nowk-1,nowpos-1,fang^1))%mod;
 
 
    }
    else  //向左
    {
        ans=(ans+dfs(nowk,nowpos-1,fang))%mod;
 
        ans=(ans+dfs(nowk-1,nowpos+1,fang^1))%mod;
 
    }
 
    if(dp[nowk][nowpos][fang]==-1)
    dp[nowk][nowpos][fang]=ans;
    else
    {
        dp[nowk][nowpos][fang]=(dp[nowk][nowpos][fang]+ans)%mod;
 
    }
 
    return  dp[nowk][nowpos][fang]%mod;
 
 
}
int main ()
{
 
 
    int t;
    cin>>t;
 
    while(t--)
    {
        cin>>n>>k;
 
        for(int i=0;i<=n;i++)
        {
            for(int j=1;j<=k;j++)
            {
                dp[j][i][1]=-1;
 
 
                dp[j][i][0]=-1;
            }
        }
        cout<<dfs(k,1,1)<<'\n';
 
 
 
    }
 
 
    return 0;
 
}