ZOJ 3924 Musical Notes

Description

Besides his skills of playing Hearthstone, Bob is also insterested in learning piano in order to make himself more charming, of course, to Alice.

Now, Bob had transcribed a musical score for himself to practice. Unfortunately, he only copied the numbered musical notation, which use numbers 1 to 7 representing the musical notes(sung as do, re, mi...) and he forgot to mark the musical notes, which means he did't know the lengths of those notes. Bob remembered that the composition contains m bar and k

Knowing  m and 

k, he can calculate the whole length of those musical notes, 

l beats, which equals 

4*m-k beats. Then he counted out 

n, the number of notes represented by number 1 to 7, with which he may find out how the composition is formed, namely finding out the length of each note. He thought there might be too many cases to form the composition, so he want you to find out the number of possible ways to form the composition.

Input

The first line of input contains an integer T (T ≤ 20) . T is the number of the cases. In the next T lines, there are three integer m, k, n, representing the number of bars, the number of quarter rests, and the number of musical notes.(1 ≤ m ≤ 10000, 0 ≤ k ≤ 3, m ≤ n ≤ m+13)

Output

The output contains T

Sample Input

12 0 5      

Sample Output

75      

Hint

The number of whole, half, quarter, eighth, sixteenth notes can be:

0, 3, 2, 0, 0. In this situation we may find 10 ways to form the composition.

1, 0, 4, 0, 0. In this situation we may find 5 ways.

1, 1, 1, 2, 0. In this situation we may find 60 ways.

簡化一下，題意就是說有5種節拍分别是4，2，1，0.5，0.25然後總共有n個，這些節拍的和是4*m-k

并且呢，n的範圍是[m,m+13]，問的是這樣的組合方案有多少種，于是直接dfs找出全部的可能乘上組合數

因為直接求組合數比較麻煩，我是直接用全排列除掉各自的排列數得到答案的，因為要取餘，是以事先算好

#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int maxn=1e4+10;
int a[5]={16,8,4,2,1};
int b[5];
int T,n,k,m;
LL ans,f[maxn],c[maxn];

LL inv(LL x, LL m)  
{  
    if (x == 1) return x;  
    return inv(m % x, m)*(m - m / x) % m;  
}  

void init()
{
    c[0]=f[0]=1;
    for (int i=1;i<maxn;i++) 
    {
        c[i]=c[i-1]*i%mod;
        f[i]=inv(c[i],mod);
    }
}

void dfs(int x,int y,int z)
{
    if (x*a[z]<y) return;
    if (z==4)
    {
        if (x==y)
        {
            b[4]=x;
            LL temp=c[n];
            for (int i=0;i<5;i++) temp=temp*f[b[i]]%mod;
            (ans+=temp)%=mod;
        }
        return;
    }
    for (int i=0;i<=x;i++)
    {
        b[z]=i;
        dfs(x-i,y-a[z]*i,z+1);
    }
}

int main()
{
    init();
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&m,&k,&n);
        ans=0;
        dfs(n,16*m-4*k,0);
        printf("%lld\n",ans);
    }
    return 0;
}