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

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

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)
    
    
    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()

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

mod = 10**9 + 7


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


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])