HDU 4906 Our happy ending（2014 Multi-University Training Contest 4）

#include<cstring>
#include<cstdio>
#include<cmath>
#include <iostream>
#include<algorithm>
#define LL long long
#define MOD 1000000007
#define debug(x) printf(#x"=%d\n",x);
using namespace std;
int d[(1<<20)+50];
int main()
{
    int tt,n,k,L;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d%d",&n,&k,&L);
        memset(d,0,sizeof(d));
        d[0]=1;
        int w=(1<<k)-1;
        int tot=0;
        if(L>k)
        {
            tot=L-k;
            L=k;
        }
        while(n--)
        {
            for(int i=w;i>=0;--i)
            {
                if(d[i]==0)continue;
                int now=d[i];
                LL tmp=((LL)tot*d[i])%MOD;
                for(int j=1;j<=L;++j)
                {
                    int sta=i|(1<<(j-1))|((i<<j)&w);
                    d[sta]+=now;
                    if(d[sta]>MOD)d[sta]-=MOD;
                }
                d[i]+=tmp;
                if(d[i]>MOD)d[i]-=MOD;
            }
        }
        int ans=0;
        for(int i=0;i<=w;++i)
            if((i>>(k-1))&1)
            {
                ans+=d[i];
                if(ans>MOD)
                    ans-=MOD;
            }
        printf("%d\n",ans);
    }
}