**Century Coder

Century Coder

All submissions for this problem are available.

Pankaj, the right arm fast bowler bowls B regular balls and at most N free-hit balls due to his inconsistent line and length. Now, If a batsman scores 0 runs of a ball, then the ball is considered to be a 'dot ball'. The batsman can either play a single ball bowled as a dot ball, or may score 1, 2, 4 or 6 runs from it. This scoring principle is same for both the regular balls as well as for the free-hit balls. The cricket match can end due to one of the following reasons.

• Either there are no regular balls remaining (irrespective of the number of free-hit balls remaining).
• Or the batsman scores 100 or more runs(irrespective of the number of regular balls or 'no-balls' remaining).

The batting side wins the game if the batsman scores 100 or more runs. Also, since the batsman is a power hitter, he never plays three continuous regular balls as dot balls. Three regular balls are considered continuous even if there are free-hit balls bowled in between them. The free-hit balls although offer a good opportunity to the batsman to score runs but they are actually served as penalty on the part of bowler and hence, not taken into consideration of counting them as a regular ball. For example, if the bowler delivers the following sequence of balls i.e [regular ball][regular ball][free-hit ball][regular ball]. Then, it is not possible to score zero runs of all the three regular balls, irrespective of the runs scored from the free-hit balls between them.

Find the number of ways in which the batting side wins the game. Since the answer can be too large, print it modulo 10^9 + 7.

Note

Do not confuse with actual rules of cricket like extra runs for no ball. Only the rules stated in the problem statement are valid.

Input

• The first line of the input contains an integer T denoting the number of test cases.
• The first line of each test case contains two space separated integers i.e B and N denoting the number of regular balls and free-hit balls respectively.

Output

• For each test case, print the number of ways in which he can win the game modulo 10^9 + 7

Constraints

• 1 ≤ T ≤ 30
• 1 ≤ B ≤ 200
• 0 ≤ N ≤ 100

Example

Input:
1
17 0

Output:
18

Explanation

For the test case, the possible ways of winning are either scoring 6 runs out of all the 17 balls, or scoring 4 runs of 1 of the balls, and 6 runs out of the rest of them.

-------------------------------------------------------------------EDITORIAL-------------------------------------------------------------------------

MAIN THING WHICH  IS  MISSING IN THE QUESTION STATEMENT AS SOON AS THE REGULAR BALL ENDS GAME WILL TERMINATE 

REST IMPLEMENTATION IS STRAIGHT ,,

-----------------------------------------------------------------------------------------CODE-------------------------------------------------------------

//Love Sucks!!!

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define Sl(x) scanf("%lld",&x)

#define Su(x) scanf("%llu",&x)

#define all(v) v.begin(),v.end()

#define Sc(x) scanf("%d",&x)

#define P(x) printf("%d", x)

#define nl() printf("\n");

#define F first

#define S second

#define MOD 1000000007

#define pb push_back

#define mp make_pair

#define mem(x,i) memset(x,i,sizeof(x))

#define fori(i,s,n) for(int i=(s);i<(n);++i)

#define ford(i,s,n) for(int i=(n)-1;i>=(s);--i)

#define INF 8944674407370955161LL

#define debug(i,st,arr) fori(i,0,st){cout<<arr[i]<<" ";}cout<<endl;

#define forci(i,sw) for((i)=(sw).begin();(i)!=(sw).end();(i)++)

#define forcd(i,sw) for((i)=(sw).rbegin();(i)!=(sw).rend();(i)++)

#define sync() ios_base::sync_with_stdio(0)

ll abs(ll x) {if(x < 0) return -x; return x;}

int addmod(int v1, int v2) {

    int v3 = v1+v2;

    if(v3 >= MOD) v3 -= MOD;

    return v3;

}

#define MAX 1805//maximum value of n goes here!!

int b, n;

int dp[205][110][110][3];

ll rec(int i, int j, int r, int dt){

    if(r >= 100)

        return 1;

    if(i == 0)

{

        return (r >= 100);

    }

    if(dp[i][j][r][dt] != -1)

        return dp[i][j][r][dt];

    ll ret = 0;

    ret = (rec(i-1, j, r+1, 0) + rec(i-1, j, r+2, 0) + rec(i-1, j, r+4, 0) + rec(i-1, j, r+6, 0))%MOD;

    ret %= MOD;

    if(dt < 2)

        ret += rec(i-1, j, r, dt+1);

    ret %= MOD;

    if(j > 0)

        ret = (ret + (rec(i, j-1, r+1, dt) + rec(i, j-1, r+2, dt) + rec(i, j-1, r+4, dt) + rec(i, j-1, r+6, dt) + rec(i, j-1, r, dt))%MOD)%MOD;

    dp[i][j][r][dt] = (int)ret;

    return ret;

}

int main()

{

    int t;

    Sc(t);

    mem(dp, -1);

    while(t--){

        Sc(b);

        Sc(n);

        printf("%d\n", (int)rec(b, n, 0, 0));

    }

    return 0;

}

int main() { //freopen("in2.txt", "r", stdin); //freopen("out.txt", "w", stdout); int t; Sc(t); mem(dp, -1); while(t--){ Sc(b); Sc(n); printf("%d\n", (int)rec(b, n, 0, 0)); } return 0; }