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: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
s = len(input())
dp = [[0] * (2 * s + 2) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    for j in range(min(i + 1, 2 * s + 1)):
        if j:
            dp[i][j] = dp[i - 1][j - 1] * 2 + dp[i - 1][j + 1] % mod
        else:
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j + 1] % mod

            
print(dp[n][s] * pow(pow(2, s, mod), mod - 2, mod) % mod)

Submission status: Wrong Answer

Solution code:
# dp[i][j][k] := i 文字目まで見て、j 文字できてて、k 文字は余計に打ってて後で消す
mod = 10**9+7
N = int(input())
if N > 300:
    exit()
S = input()
J = len(S)
dp = [[0]*(N-J+2) for _ in range(J+1)]
dp[0][0] = 1
for _ in range(N):
    dp_new = [[0]*(N-J+2) for _ in range(J+1)]
    for j in range(J+1):
        for k in range(N-J+1):
            dp_new[j][k] = dp[j][k+1]
            if k==0 and j != 0:
                dp_new[j][k] += dp[j-1][k]
            if k!=0:
                dp_new[j][k] += dp[j][k-1] << 1
            if j==k==0:
                dp_new[j][k] += dp[j][k]
            dp_new[j][k] %= mod
    dp = dp_new
print(dp[J][0])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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][0] = sum(dp[src][0:2])%MOD
    dp[tgt][-1] = (2*dp[src][-2])%MOD
    for j in range(1,N+n-1):
        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)
# print(dp)

Submission status: Wrong Answer

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

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

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


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

for n in range(1, N + 1):
	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: Wrong Answer

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

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

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

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

for n in range(1, N + 1):
	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: Wrong Answer

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

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

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


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

for n in range(1, N + 1):
	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: Time Limit Exceeded

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

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

for i in range(n):
    for j in range(n):
        if(j==0):
            dp[i+1][0] += dp[i][0]
            dp[i+1][0] %= mod
            dp[i+1][1] += dp[i][0]*2
            dp[i+1][1] %= mod
        else:
            dp[i+1][j-1] += dp[i][j]
            dp[i+1][j-1] %= mod
            dp[i+1][j+1] += dp[i][j]*2
            dp[i+1][j+1] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
m = len(input())

mod = 10**9 + 7
# dp[i][j] = i文字打ってj文字入力されてる0or1 とBの打ち方
dp = [[0]*(n+1) for i in range(n+1)]

dp[0][0] = 1

# 遷移 : dp[i][j] →dp[i+1][j+1]+ dp[i+1][max(j-1,0)]+
for i in range(n):
    for j in range(n):
        dp[i+1][j+1] += dp[i][j]
        dp[i+1][j+1] %= mod
        dp[i+1][max(j-1,0)] += dp[i][j]*(2 - (j==0))
        dp[i+1][max(j-1,0)] %= mod
print(dp[n][m])

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int,readline().split())
s = input()


dp = [[0]*(n+1) for _ in range(n+1)] # iまで見て k文字、jまで一致
dp[0][0] = 1

MOD = 10**9+7
for i in range(n):
    ndp = [[0]*(n+1) for _ in range(n+1)] # iまで見て k文字、jまで一致
    for k in range(i+1):
        for j in range(k+1):
            if dp[k][j]:
                if k==0:
                    ndp[0][0] += dp[0][0]
                    ndp[0][0] %= MOD
                elif j==k:
                    ndp[k-1][j-1] += dp[k][j]
                    ndp[k-1][j-1] %= MOD
                else:
                    ndp[k-1][j] += dp[k][j]
                    ndp[k-1][j] %= MOD
                
                if j==k:
                    ndp[k+1][j] += dp[k][j]
                    ndp[k+1][j] %= MOD
                    ndp[k+1][j+1] += dp[k][j]
                    ndp[k+1][j+1] %= MOD

                else:
                    ndp[k+1][j] += 2*dp[k][j]
                    ndp[k+1][j] %= MOD
    dp = ndp
    #print(dp)

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

Submission status: Time Limit Exceeded

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]*2**j+dp[i-1][j+1]*2**(j+1)
        elif j==n:
            dp[i][j]+=dp[i-1][j-1]*2*2**(j-1)
        else:
            dp[i][j]+=dp[i-1][j-1]*2*2**(j-1)+dp[i-1][j+1]*2**(j+1)
        dp[i][j]//=2**j
        dp[i][j]%=mod

print(dp[n][m]%mod)
#print((dp[n][m]//(pow(2,m)))%mod)

Submission status: Time Limit Exceeded

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,min(n,i+1)):
    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: Time Limit Exceeded

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: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
M=len(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: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
import math
import array
def ext_gcd(a,b):
    """returns tuple (gcd(a,b), x, y) s.t. ax+by=gcd(a,b)"""
    if b==0:
        return (a,1,0)
    g,x,y = ext_gcd(b,a%b) 
    return (g,y,x-a//b*y)
def invmod(a,P):
    _,x,y = ext_gcd(a,P)
    return (x+P) % P

N = int(input())
S = input()
M = len(S)
P = int(1e9+7)
zeros = array.array('L', [0 for _ in range(N+1)])
dp = array.array('L', zeros)
dp[0] = 1
for n in range(N):
    ndp = array.array('L', zeros)
    for m in range(max(0,M-(N-n)), min(n,M+(N-n))+1):
        c = dp[m]%P
        ndp[max(0,m-1)] += c
        ndp[m+1] += c*2
    dp = ndp

print((dp[M]*invmod(2**M,P))%P) # !

Submission status: Time Limit Exceeded

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

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

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


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

for n in range(1, N + 1):
	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: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
n = int(input())
l = len(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: Time Limit Exceeded

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]
        else:dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]*2
print dp[n][l]%mod

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def i():
    return int(raw_input())
def s():
    return raw_input()
 
#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper
 
Q=10**9+7
@memoize
def dp(n,i):
    if n<i:return 0
    elif n==1:return 1
    if i==0:return (dp(n-1,1)*2+dp(n-1,0))%Q
    else:return (dp(n-1,i-1)+dp(n-1,i+1)*2)%Q
n=i()
s=s()
print dp(n,len(s))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def i():
    return int(raw_input())
def s():
    return raw_input()
 
#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper
 
Q=10**9+7
@memoize
def dp(n,i):
    if n<i:return 0
    elif n==1:return 1
    if i==0:return (dp(n-1,1)*2+dp(n-1,0))%Q
    else:return (dp(n-1,i-1)+dp(n-1,i+1)*2)%Q
n=i()
s=s()
print dp(n,len(s))

Submission status: Time Limit Exceeded

Solution code:
n = input()
s = raw_input()

MOD = 10**9+7
dp = [1]
for i in xrange(n):
    dp2 = [0]*(i+2)
    for j in xrange(i+1):
        dp2[j+1] += dp[j]
        dp2[j+1] %= MOD
    for j in xrange(1, i+1):
        dp2[j-1] += 2*dp[j]
        dp2[j-1] %= MOD
    dp2[0] = (dp2[0] + dp[0]) % MOD
    dp = dp2
print dp2[len(s)]

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

###########
Q=10**9+7
@memoize
def dp(n,i):
    if n<i:
        return 0
    elif n==1:
        return 1
    if i==0:
        return (dp(n-1,1)*2+dp(n-1,0))%Q
    else:
        return (dp(n-1,i-1)+dp(n-1,i+1)*2)%Q

n=i()
s=s()
print dp(n,len(s))

Submission status: Memory Limit Exceeded

Solution code:
def main():
  mod=10**9+7
  n=int(input())
  m=len(input())
  dp=[[0]*(n+1) for _ in range(n+1)]
  dp[0][0]=1
  for i in range(n):
    for j in range(n):
      dp[i+1][j+1]=(dp[i][j]+dp[i+1][j+1])%mod
      dp[i+1][j]=(dp[i+1][j]+dp[i][j+1]*2)%mod
    dp[i+1][0]=(dp[i+1][0]+dp[i][0])%mod
  print(dp[n][m])
main()

Submission status: Memory Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
s = len(input())
dp = [[0] * (n + 2) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    nxt = [0] * (n + 1)
    for j in range(n + 1):
        if j:
            dp[i][j] = (dp[i - 1][j - 1] * 2 + dp[i - 1][j + 1]) % mod
        else:
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j + 1]) % mod


print(dp[n][s] * pow(pow(2, s, mod), mod - 2, mod) % mod)

Submission status: Memory Limit Exceeded

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    s=input()
    t=len(s)
    #文字数が同じなら通り数は一緒なので文字数だけ見る
    
    dp=[[0]*(N+1) for _ in range(N+1)]
    #i回操作して，j文字になる
    
    dp[0][0]=1
    for i in range(N):
        for j in range(i+1):
            if j!=0:
                dp[i+1][j-1]=(dp[i+1][j-1] + dp[i][j])%mod
            else:
                dp[i+1][0]=(dp[i+1][0]+dp[i][0])%mod
            dp[i+1][j+1]=(dp[i+1][j+1] + 2*dp[i][j])%mod
    
    temp=pow(2,t,mod)            
    ans=(dp[-1][t]*pow(temp,mod-2,mod))%mod
    print(ans)

main()

Submission status: Memory Limit Exceeded

Solution code:
n = int(input())
m = len(input())

mod = 10**9 + 7

# dp[i][j] = i文字打ってj文字入力されてる0or1 とBの打ち方
dp = [[0]*(n+1) for i in range(n+1)]

dp[0][0] = 1

# 遷移 : dp[i][j] →dp[i+1][j+1]+ dp[i+1][max(j-1,0)]+
for i in range(n):
    for j in range(n):
        dp[i+1][j+1] += dp[i][j]
        dp[i+1][j+1] %= mod
        dp[i+1][max(j-1,0)] += dp[i][j]*(2 - (j==0))%mod
        dp[i+1][max(j-1,0)] %= mod
print(dp[n][m])

Submission status: Memory Limit Exceeded

Solution code:
N=int(input())
s=input()
K=len(s)
mod=10**9+7
dp=[[0 for i in range(N+1)] for i in range(N+1)]
dp[0][0]=1
for i in range(N):
  for j in range(N):
    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)
inv=power(2**K,mod-2)
print((dp[N][K]*inv)%mod)

Submission status: Memory Limit Exceeded

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

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

dp = [[0 for i in range(N + 2)] for j 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: Memory Limit Exceeded

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

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

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

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:
def main():
  mod=10**9+7
  n=int(input())
  m=len(input())
  dp=[[0]*(n+1) for _ in range(2)]
  dp[0][0]=1
  for i in range(n):
    for j in range(n+1):
      dp[(i+1)&1][j]=0
    for j in range(n):
      dp[(i+1)&1][j+1]=(dp[i&1][j]+dp[(i+1)&1][j+1])%mod
      dp[(i+1)&1][j]=(dp[(i+1)&1][j]+dp[i&1][j+1]*2)%mod
    dp[(i+1)&1][0]=(dp[(i+1)&1][0]+dp[i&1][0])%mod
  print(dp[n&1][m])
main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
s = len(input())
dp = [0] * (n + 2)
dp[0] = 1
for i in range(1, n + 1):
    ndp = [0] * (n + 2)
    for j in range(n + 1):
        if j:
            ndp[j] = (dp[j - 1] * 2 + dp[j + 1]) % mod
        else:
            ndp[j] = (dp[j] + dp[j + 1]) % mod
    dp = ndp


print(dp[s] * pow(pow(2, s, mod), mod - 2, mod) % mod)

Submission status: Accepted

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

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

for i in range(n):
    next = [0] * (n+1)
    for j in range(n):
        if(j==0):
            next[0] += dp[0]
            next[0] %= mod
            next[1] += dp[0]*2
            next[1] %= mod
        else:
            next[j-1] += dp[j]
            next[j-1] %= mod
            next[j+1] += dp[j]*2
            next[j+1] %= mod
    dp = next[::]

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

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    s=input()
    t=len(s)
    #文字数が同じなら通り数は一緒なので文字数だけ見る
    
    now=[0]*(N+5)
    nxt=[0]*(N+5)
    #i回操作して，j文字になる
    
    now[0]=1
    for i in range(N):
        for j in range(i+1):
            if j!=0:
                nxt[j-1]=(nxt[j-1] + now[j])%mod
            else:
                nxt[0]=(nxt[0]+now[0])%mod
            nxt[j+1]=(nxt[j+1] + 2*now[j])%mod
        for j in range(i+2):
            now[j]=nxt[j]
            nxt[j]=0
            
    
    temp=pow(2,t,mod)            
    ans=(now[t]*pow(temp,mod-2,mod))%mod
    print(ans)

main()

Submission status: Accepted

Solution code:
n = int(input())
m = len(input())

mod = 10**9 + 7

# dp[i][j] = i文字打ってj文字入力されてる0or1 とBの打ち方
dp = [0]*(n+1)
dp[0] = 1

# 遷移 : dp[i][j] →dp[i+1][j+1]+ dp[i+1][max(j-1,0)]+
for i in range(n):
    dpnxt = [0]*(n+1)
    for j in range(n):
        dpnxt[j+1] += dp[j]
        dpnxt[j+1] %= mod
        dpnxt[max(j-1,0)] += dp[j]*(2 - (j==0))%mod
        dpnxt[max(j-1,0)] %= mod
    dp = dpnxt.copy()
print(dp[m])