D. Carry Bit

很好转化题意 发现就是一个进位就会产生1贡献
那我们发现要产生进位 至少在低位会有一个1 1出现
然后接着下一位我们要让他继续进位的话只有 01 10 11三种选择 00则会断掉进位
所以对于每一个长度为n的数组来说 我们要找出有k个进位的方案数
我们可以先枚举我们进位段有i个 我们有k个 我们直接用隔板法算出为C k-1 i-1
而为进位末端一定是11进位前端要是前面还有的话一定是00
这时候我们会发现首尾如果放进位段和不进位段的计算情况还是不一样的！
那我们就必须分2*2种情况讨论了
我们要讨论的就是i段下 有多少个位置是被固定了只能放00 或者 11
其他位置显然我们可以放3种 还有就是不进位有多少段 我们还是用隔板法算出即可
最后把答案加起来
注意我们C 0 0 还是要算成1 不然会漏解

int a[N],b[N],pow3[N];
int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1)res=(res*a)%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
int C(int x,int y){
    if(x<0||y<0||x<y)return 0;
    return a[x]*b[y]%mod*b[x-y]%mod;
}
inline int get(int x, int y){
    if (x == y) return 1;
    if (x == 0) return 0;
    return C(x - 1, y - 1);
}
void solve(){
    int n,k;cin>>n>>k;
    int ans=0;
    if(k==0){
        cout<<pow3[n]<<endl;
        return;
    }
    for(int i=0;i<=k;i++){
        if(n-2*i>=0){
            (ans+=pow3[n-2*i]*get(k,i)%mod*get(n-k,i+1)%mod)%=mod;
            (ans+=pow3[n-2*i]*get(k,i)%mod*get(n-k,i)%mod)%=mod;
        }
        if(n-2*i+1>=0){
            (ans+=pow3[n-2*i+1]*get(k,i)%mod*get(n-k,i)%mod)%=mod;
            (ans+=pow3[n-2*i+1]*get(k,i)%mod*get(n-k,i-1)%mod)%=mod;
        }
    }
    cout<<ans<<endl;
}