Problem:


Score : 800 points

Problem Statement

Sig has built his own keyboard. Designed for ultimate simplicity, this keyboard only has 3 keys on it: the 0 key, the 1 key and the backspace key.

To begin with, he is using a plain text editor with this keyboard. This editor always displays one string (possibly empty). Just after the editor is launched, this string is empty. When each key on the keyboard is pressed, the following changes occur to the string:

The 0 key: a letter 0 will be inserted to the right of the string.

The 1 key: a letter 1 will be inserted to the right of the string.

The backspace key: if the string is empty, nothing happens. Otherwise, the rightmost letter of the string is deleted.

Sig has launched the editor, and pressed these keys N times in total. As a result, the editor displays a string s. Find the number of such ways to press the keys, modulo 10^9 + 7.

Constraints

1 ≦ N ≦ 5000

1 ≦ |s| ≦ N

s consists of the letters 0 and 1.

Partial Score

400 points will be awarded for passing the test set satisfying 1 ≦ N ≦ 300.

Input

The input is given from Standard Input in the following format:

N
s

Output

Print the number of the ways to press the keys N times in total such that the editor displays the string s in the end, modulo 10^9+7.

Sample Input 1

3
0

Sample Output 1

5

We will denote the backspace key by B. The following 5 ways to press the keys will cause the editor to display the string 0 in the end: 00B, 01B, 0B0, 1B0, BB0. In the last way, nothing will happen when the backspace key is pressed.

Sample Input 2

300
1100100

Sample Output 2

519054663

Sample Input 3

5000
01000001011101000100001101101111011001000110010101110010000

Sample Output 3

500886057



Sample input:
3
0


Sample output:
5

Submission status: Accepted

Solution code:
n = int(input())
s = input()
MOD = 10 ** 9 + 7

# dp[i][j]
# i回目のキーを押し終えたときに、文字列の長さがjになるときの通り数
dp = [[0] * (n + 1) for i in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    for j in range(n + 1):
        # Bを押したとき
        dp[i + 1][max(j - 1, 0)] += dp[i][j]
        dp[i + 1][max(j - 1, 0)] %= MOD
        if j + 1 <= n:
            # 0を押したとき
            dp[i + 1][j + 1] += dp[i][j]
            # 1を押したとき
            dp[i + 1][j + 1] += dp[i][j]
            dp[i + 1][j + 1] %= MOD

ptn = pow(2, len(s), MOD)
print(dp[-1][len(s)] * pow(ptn, MOD - 2, MOD) % MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9+7

n = int(input())
l = len(input().rstrip())
dp = [[0]*(i+1) for i in range(n+1)]
for i in range(n+1):
  for j in range(i+1):
    if i == 0:
      dp[0][0] = 1
    else:
      dp[i][j] = dp[i-1][max(j-1, 0)]
      if i-1 >= j+1:
        dp[i][j] += 2*dp[i-1][j+1]
      dp[i][j] %= MOD
ans = dp[n][l]
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
m=len(input())
mod=10**9+7

dp=[[0 for j in range(i+2)] for i in range(N+1)]
dp[N][m]=1
for i in range(N-1,-1,-1):
    for j in range(1,i+2):
        dp[i][j]=(2*dp[i+1][j-1]+dp[i+1][j+1])%mod
    dp[i][0]=(dp[i+1][0]+dp[i+1][1])%mod

print(dp[0][0])

Submission status: Accepted

Solution code:
n = int(input())
s = input()
l = len(s)
mod = 10**9+7
dp = [[0 for i in range(j+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  if i == 1:
    dp[1][0] = 1
  else:
    dp[i][0] = dp[i-1][1]*2+dp[i-1][0]
  dp[i][0] %= mod
  for j in range(1,i+1):
    if j < i-1:
      dp[i][j] = 2*dp[i-1][j+1]
    dp[i][j] += dp[i-1][j-1]
    dp[i][j] %= mod
print(dp[n][l])

Submission status: Accepted

Solution code:
n=int(input())
p=[0]*5001
p[len(input())]=1
while n:
	p=[((2*p[j-1]if j else p[j])+p[j+1])%(10**9+7)for j in range(n)]
	n=n-1
print(p[0])

Submission status: Accepted

Solution code:
d=10**9+7
n=int(input())
p=[0]*5001
p[len(input())]=1
while n:
	p=[((2*p[j-1]if j else p[j])+p[j+1])%d for j in range(n)]
	n=n-1
print(p[0])

Submission status: Accepted

Solution code:
N=int(input())
s=input()
n=len(s)
MOD = 10**9+7
dp = [[0]*(N+n+1) for _ in range(2)]
dp[0][0] = 1
for i in range(N):
    src = i%2
    tgt = (i+1)%2
    dp[tgt][-1] = (2*dp[src][-2])%MOD
    dp[tgt][0] = sum(dp[src][0:2])%MOD
    for j in range(1,N+n):
        dp[tgt][j] = (dp[src][j-1]*2 + dp[src][j+1])%MOD
tmp = pow(2**n,MOD-2,MOD)
res = (dp[N%2][n]*tmp)%MOD
print(res)

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc059/tasks/arc059_d

dp[i][j] = i回キーボードを押した時に、j文字の通り数
とすれば、O(N**2)で解ける。

0,1は等確率で現れることを考えれば、文字数を減らした場合のdp推移も簡単。
2(mod10**9+7)の逆元が必要かな→いらんかった

(最後に|s|文字になっている押し方/2**|s|)通りが求める答え
"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)


N = int(input())

s = input()

dp = [0] * (N+1)
dp[0] = 1

mod = 10**9+7

for loop in range(N):

    ndp = [0] * (N+1)

    for i in range(N+1):

        dp[i] %= mod
        if i != N:
            ndp[i+1] += dp[i] * 2
            ndp[i+1] %= mod

        if i != 0:
            ndp[i-1] += dp[i]
            ndp[i-1] %= mod
        else:
            ndp[i] += dp[i]
            ndp[i] %= mod

    dp = ndp

    #print (dp)
inv = inverse(pow(2,len(s),mod) , mod)
print (dp[len(s)] * inv % mod)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
m=len(s)
mod=10**9+7
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(n+1):
        if j==0:
            dp[i][j]+=dp[i-1][j]+dp[i-1][j+1]
        elif j==n:
            dp[i][j]+=dp[i-1][j-1]*2
        else:
            dp[i][j]+=dp[i-1][j-1]*2+dp[i-1][j+1]
        dp[i][j]%=mod
def div(a,b):
    return (a*pow(b,mod-2,mod))%mod
print(div(dp[n][m],pow(2,m)))

Submission status: Accepted

Solution code:
P = 10**9+7
fa = [1]
for i in range(1, 50000):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, 50000)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]
p2 = [1]
for _ in range(1, 50000):
    p2.append(p2[-1] * 2 % P)
def F(a, b):
    if a < 0 or b < 0: return 0
    return fa[a+b] * fainv[a] % P * fainv[b] % P

N = int(input())
S = input()
M = len(S)
ans = 0
for i in range(5001):
    for j in range(i + (N + M & 1), min(5001, N-M-i+1), 2):
        a = (N+M-i-j) // 2
        b = a - M
        a -= 1
        ans = (ans + (F(i, j) - F(i-1, j+1)) * (F(a, b) - F(a+1, b-1)) * p2[i+b]) % P

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

mod = 10**9 + 7
M=len(S)

DP = [[0]*(N+1) for i in range(N+1)]

DP[0][0] = 1

for i in range(1,N+1):
    for j in range(N+1):
        if j>0 and j<N:
            DP[i][j] = DP[i-1][j-1] + 2*DP[i-1][j+1]
        elif j==0:
            DP[i][j] = DP[i-1][j] + 2*DP[i-1][j+1]
        else:
            DP[i][j] = DP[i-1][j-1]
        DP[i][j] %= mod

print(DP[N][M])

Submission status: Accepted

Solution code:
n = int(input())
s = len(input())
mod = 10**9+7
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  dp[i][0] = (dp[i-1][0] + dp[i-1][1])%mod
  for j in range(1,n):
    dp[i][j] = (dp[i-1][j-1]*2 + dp[i-1][j+1])%mod
  dp[i][n] = dp[i-1][n-1]*2%mod
s2 = pow(2,s,mod)
rev = pow(s2,mod-2,mod)
print(dp[n][s]*rev%mod)

Submission status: Accepted

Solution code:
N = int(input())
s = input()
mod = 10 ** 9 + 7


def main():
    dp = [[0 for _ in range(N+1)] for _ in range(2)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(N):
            dp[(i+1)%2][j] = 0
        for j in range(N):
            dp[(i+1)%2][j+1] = (dp[(i+1)%2][j+1] + dp[i%2][j] * 2) % mod
            if j-1 >= 0:
                dp[(i+1)%2][j-1] = (dp[(i+1)%2][j-1] + dp[i%2][j]) % mod
            else:
                dp[(i+1)%2][j] = (dp[(i+1)%2][j] + dp[i%2][j]) % mod

    pow2 = pow(2, len(s), mod)
    inv_pow2 = pow(pow2, mod-2, mod)
    print((dp[N%2][len(s)] * inv_pow2) % mod)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
n = int(input())
s = input().rstrip()
m = len(s)

dp = [[0] * (n + 3) for _ in range(n + 3)]
dp[0][0] = 1

for i in range(1, n + 1):
    dp[0][i] += dp[0][i-1]
    dp[0][i] %= MOD
    for j in range(i + 1):
        # Delete
        dp[j-1][i] += dp[j][i-1]
        # Add
        dp[j+1][i] += dp[j][i-1] * 2
        dp[j+1][i] %= MOD

div2 = pow(2, MOD-2, MOD)
ans = dp[m][n]
for i in range(m):
    ans *= div2
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
O=10**9+7
D=[1]+[0]*input()
M=len(raw_input())
for _ in D[1:]:D=[D[0]+D[1]]+[(i+2*j)%O for i,j in zip(D[2:]+[0],D[:-1])]
print D[M]*(-~O/2)**M%O

Submission status: Accepted

Solution code:
N=input()
M=len(raw_input())
O=10**9+7
D=[pow(-~O/2,M,O)]+[0]*N
for _ in'_'*N:D=[D[0]+D[1]]+[(i+2*j)%O for i,j in zip(D[2:]+[0],D[:-1])]
print D[M]

Submission status: Accepted

Solution code:
N=input()
M=len(raw_input())
O=10**9+7
D=[pow(-~O//2,M,O)]+[0]*N
for _ in'_'*N:D=[D[0]+D[1]]+[(i+2*j)%O for i,j in zip(D[2:]+[0],D[:-1])]
print D[M]

Submission status: Accepted

Solution code:
N=int(input())
M=len(input())
O=10**9+7
D=[pow(-~O//2,M,O)]+[0]*-~N
for _ in'_'*N:D=[((2*D[i-1]if i else D[0])+D[i+1])%O for i in range(N+1)]+[0]
print(D[M])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

"""
0,1の配置は関係ない。文字列長だけが問題。
"""

MOD = 10**9 + 7
N = int(input())
S = input().rstrip()

LS = len(S)

# 長さ、何通り
dp = np.zeros(N+1, dtype=np.int64)
dp[0] = 1
for _ in range(N):
    prev = dp
    dp = np.zeros_like(prev)
    # 文字の追加
    dp[1:] += 2*prev[:-1]
    # 文字の削除
    dp[:-1] += prev[1:]
    dp[0] += prev[0]
    dp %= MOD

x = dp[LS]
answer = x * pow((1+MOD)//2,LS,MOD) % MOD
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
s = len(input())

mod = 10**9 + 7
dp = [1] + [0]*N
for i in range(N):
    dp = [dp[0] + dp[1]] + [(i + 2*j) % mod for i, j in zip(dp[2:] + [0],dp[:-1])]
print(dp[s]*pow(2**s, mod - 2, mod)%mod)

Submission status: Accepted

Solution code:
N=int(input())
s=input()
K=len(s)
mod=10**9+7
dp=[]
for i in range(N+1):
  dp.append([0]*(i+1))
dp[0][0]=1
for i in range(N):
  for j in range(i+1):
    if j>=1:
      dp[i+1][j-1]+=dp[i][j]
    else:
      dp[i+1][j]+=dp[i][j]
    dp[i+1][j+1]+=2*dp[i][j]
    dp[i+1][j-1]%=mod
    dp[i+1][j+1]%=mod
def power(x,y):
  if y==0:
    return 1
  if y==1:
    return x%mod
  if y==2:
    return (x*x)%mod
  if y%2:
    return (power(power(x,(y-1)//2),2)*x)%mod
  else:
    return power(power(x,y//2),2)
a=power(2,K)
inv=power(a,mod-2)
print((dp[N][K]*inv)%mod)

Submission status: Accepted

Solution code:
N=int(input())
s=input()
l=len(s)
dp=[[0]*(N+2) for i in range(N)]
dp[0][1]=2
dp[0][0]=1
mod=10**9+7
for i in range(N-1):
    for j in range(i+2):
        if j==0:
            dp[i+1][j+1]+=2*dp[i][j]
            dp[i+1][j+1]%=mod
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod            
            continue
        dp[i+1][j+1]+=2*dp[i][j]
        dp[i+1][j+1]%=mod
        dp[i+1][j-1]+=dp[i][j]
        dp[i+1][j-1]%=mod  
t=pow(2,(mod-2),mod)
t=pow(t,l,mod)
print((dp[-1][l]*t)%mod)

Submission status: Accepted

Solution code:
N=int(input())
s=input()
l=len(s)
dp=[[0]*(N+1) for i in range(N)]
dp[0][1]=2
dp[0][0]=1
mod=10**9+7
for i in range(N-1):
    for j in range(N):
        if j==0:
            dp[i+1][j+1]+=2*dp[i][j]
            dp[i+1][j+1]%=mod
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod            
            continue
        if j!=N:
            dp[i+1][j+1]+=2*dp[i][j]
            dp[i+1][j+1]%=mod
        dp[i+1][j-1]+=dp[i][j]
        dp[i+1][j-1]%=mod  
t=pow(2,(mod-2),mod)
t=pow(t,l,mod)
print((dp[-1][l]*t)%mod)

Submission status: Accepted

Solution code:
MOD = (10 ** 9) + 7

N = int(input())
s = list(input())

dp = [[0] * (N + 2) for i in range(N + 1)]

for n in range(N + 1):
	for l in range(n + 1):
		if n == 1:
			dp[n][l] = 1
		elif l == 0:
			dp[n][l] = (dp[n - 1][0] + 2 * dp[n - 1][1]) % MOD
		else:
			dp[n][l] = (dp[n - 1][l - 1] + 2 * dp[n - 1][l + 1]) % MOD

print(dp[N][len(s)])

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(raw_input())
l=len(raw_input())
dp=[[0]*(n+2) for j in range(n+1)]
for i in range(n+1):
    for j in range(i+1):
        if i==0:dp[i][j]=1
        elif j==0:dp[i][j]=(dp[i-1][1]*2+dp[i-1][0])%mod
        else:dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1]*2)%mod
print dp[n][l]

Submission status: Accepted

Solution code:
mod=1000000007
n=int(raw_input())
l=len(raw_input())
dp=[[0 for i in range(n+2)] for j in range(n+1)]
for i in range(n+1):
    for j in range(i+1):
        if i==0:dp[i][j]=1
        elif j==0:dp[i][j]=(dp[i-1][1]*2+dp[i-1][0])%mod
        else:dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1]*2)%mod
print dp[n][l]

Submission status: Runtime Error

Solution code:
MOD = (10 ** 9) + 7

N = int(input())
s = list(input())

dp = [[0 for i in range(N)] for j in range(N)]


for i in range(N):
	dp[i][i] = 1
for i in range(N - 1):
	dp[i][i + 1] = 1

for n in range(1, N):
	dp[n][0] = (dp[n - 1][0] + 2 * dp[n - 1][1]) % MOD
	for l in range(1, n):
		dp[n][l] = (dp[n - 1][l - 1] + 2 * dp[n - 1][l + 1]) % MOD

print(dp[N - 1][len(s)])

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

const long long M = 1000000007;

//x^n mod M
typedef long long ull;
ull power(ull x, ull n){
	ull res = 1;
	if(n > 0){
		res = power(x, n / 2);
		if(n % 2 == 0) res = (res * res) % M;
		else res = (((res * res) % M) * x ) %M;
	}
	return res;
}

int main(){
	int n;
	string s;
	cin >> n >> s;

	vector<long long> dp(n + 1, 0);
	dp[0] = 1;
	rep(i,n){
		vector<long long> _dp(n + 1, 0);
		rep(j,n + 1){
			if(j == 0) (_dp[j] += dp[j]) %= M;
			else (_dp[j - 1] += dp[j]) %= M;
			(_dp[j + 1] += dp[j] * 2LL) %= M;
		}
		dp = _dp;
		//for(auto j : dp){ for(auto k : j){ cout << k <<  ' '; } cout << endl; } cout << endl;
	}
	cout << dp[s.size()] * power(power(2,s.size()), M - 2) % M  << endl;
}