Submission #3412900

---

Source Code Expand

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
int N,K;
ll dp[310][310][310] = {{{0}}},inf = 1e9+7;
string S;
int main(){
	cin >> N >> K >> S;
	dp[0][0][0] = 1;
	for(int i=1;i<=N;i++){
		for(int j=0;j<=K;j++){
			for(int k=0;k<=K;k++){
				if(S[i-1]=='0'){
					dp[i][j+1][max(k-1,0)] += dp[i-1][j][k];
					dp[i][j+1][max(k-1,0)] %= inf;
				}else if(S[i-1]=='1'){
					dp[i][max(j-1,0)][k+1] += dp[i-1][j][k];
					dp[i][max(j-1,0)][k+1] %= inf;
				}else{
					dp[i][j+1][max(k-1,0)] += dp[i-1][j][k];
					dp[i][j+1][max(k-1,0)] %= inf;
					dp[i][max(j-1,0)][k+1] += dp[i-1][j][k];
					dp[i][max(j-1,0)][k+1] %= inf;
				}
			}
		}
	}
	ll ans = 0;
	for(int j=0;j<=K;j++){
		for(int k=0;k<=K;k++){
			ans = (ans+dp[N][j][k])%inf;
		}
	}
	cout << ans << endl;
}

Submission Info

Judge Result