Problem:
 Score : 1100 points    Problem Statement Given is a string S consisting of 0 and 1 . Find the number of strings, modulo 998244353 , that can result from applying the following operation on S zero or more times:   Remove the two characters at the beginning of S , erase one of them, and reinsert the other somewhere in S . This operation can be applied only when S has two or more characters.       Constraints  1 \leq |S| \leq 300  S consists of 0 and 1 .         Input Input is given from Standard Input in the following format:  S       Output Print the number of strings, modulo 998244353 , that can result from applying the operation on S zero or more times.        Sample Input 1 0001      Sample Output 1 8  Eight strings, 0001 , 001 , 010 , 00 , 01 , 10 , 0 , and 1 , can result.       Sample Input 2 110001      Sample Output 2 24       Sample Input 3 11101111011111000000000110000001111100011111000000001111111110000000111111111      Sample Output 3 697354558

Solution (Python):
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353
N = 2*10**3
g1 = [1]*(N+1) 
g2 = [1]*(N+1) 
inverse = [1]*(N+1) 

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0

import time
S=input()
N=len(S)

start=time.time()
if N==1:
    exit(print(1))

dp=[[[-10**15 for i in range(N+2)] for j in range(N+2)] for k in range(N+1)]
dpf=[[[-10**15 for i in range(N+2)] for j in range(N+2)] for k in range(N+1)]

dpf[0][0][0]=1
if S[0]=="0":
    dp[1][1][0]=0
if S[1]=="0":
    dp[1][1][0]=0
if S[0]=="1":
    dp[1][0][1]=0
if S[1]=="1":
    dp[1][0][1]=0
dpf[1][0][0]=2
Zero=1-int(S[0])+1-int(S[1])
One=int(S[0])+int(S[1])
for i in range(2,N):
    Zero+=1-int(S[i])
    One+=int(S[i])
    for j in range(Zero+1):
        for k in range(One+1):
            a,b=1-int(S[i]),int(S[i])
            dp[i][j][k]=max(dp[i-1][j-a][k-b]-2,dpf[i-1][j-a][k-b]-1)
            a,b=1-int(S[i-1]),int(S[i-1])
            dpf[i][j][k]=max(dpf[i-1][j][k]+1,dp[i-1][j][k]+1-dp[i-1][j][k]%2)
            dp[i][j][k]=max(dp[i][j][k],2*(dpf[i-2][j-a][k-b]//2),2*(dp[i-2][j-a][k-b]//2))
            if dp[i][j][k]<0:
              dp[i][j][k]=-10**5
            if dpf[i][j][k]<0:
              dpf[i][j][k]=-10**5
    dpf[i][0][0]=i+1

med=time.time()


S=[S[-i-1] for i in range(N)]
Zero=0
One=0
ans=1
check=set([])
one,zero=S.count("1"),S.count("0")
for i in range(N):
    Zero+=(S[i]=="1")
    One+=(S[i]=="0")
    for j in range(zero+1):
        for k in range(one+1):
            if (dp[N-1-i][j][k]>=0 or dpf[N-1-i][j][k]>=0) and (j,k)!=(0,0):
                check.add((j,k))
    ncheck=set([])
    for j,k in check:
        A,B=1,1
        if j!=0:
            A=cmb(Zero+j-1,j,mod)
        if k!=0:
            B=cmb(One+k-1,k,mod)
        ans+=A*B
        ans%=mod
        a,b=1-int(S[i]),int(S[i])
        if j>=a and k>=b:
            ncheck.add((j-a,k-b))
    check=ncheck
    zero-=1-int(S[i])
    one-=int(S[i])

print(ans)

def check():
    res=0
    for i in range(N):
        for j in range(N+1):
            for k in range(N+1) :
                if data[i][j][k]:
                    print(i,j,k)
                    res+=1
    return res

Solution (Python):
import numpy as np
import numba as nb


@nb.njit('(i1[:],)', cache=True)
def solve(s):
    n = len(s)
    size = n // 2
    MOD = 998244353
    dp_can = np.zeros((n + 1, size + 1, size + 1), dtype=np.int8)
    dp_cnt = np.zeros((n + 1, size + 1, size + 1), dtype=np.int64)

    dp_cnt[n, 0] = 1
    for j in range(size):
        dp_cnt[n, j + 1] = np.cumsum(dp_cnt[n, j]) % MOD

    for i in range(n - 1, -1, -1):
        if s[i] == 0:
            for j in range(size + 1):
                dp_cnt[i, j] = np.cumsum(dp_cnt[i + 1, j]) % MOD
        else:
            for k in range(size + 1):
                dp_cnt[i, :, k] = np.cumsum(dp_cnt[i + 1, :, k]) % MOD

    dp_can[0, 0, 0] = 1
    for i in range(n):
        for j in range(size):
            for k in range(size):
                if dp_can[i, j, k] == 0:
                    continue
                dp_can[i + 1, j, k] = 1
                if j > 0 and s[i] == 1:
                    dp_can[i + 1, j - 1, k + 1] = 1
                if k > 0 and s[i] == 0:
                    dp_can[i + 1, j + 1, k - 1] = 1
                if i < n - 1:
                    if s[i] == 0 or s[i + 1] == 0:
                        dp_can[i + 2, j + 1, k] = 1
                    if s[i] == 1 or s[i + 1] == 1:
                        dp_can[i + 2, j, k + 1] = 1
    dp_can[1:, 0, 0] = 0

    ans = 0

    for i in range(n, -1, -1):
        for j in range(size + 1):
            for k in range(size + 1):
                if dp_can[i, j, k] == 0:
                    continue

                ans = (ans + dp_cnt[i, j, k]) % MOD

                a, b = j, k
                for h in range(i - 1, -1, -1):
                    if s[h] == 0:
                        a -= 1
                    else:
                        b -= 1
                    if a < 0 or b < 0:
                        break
                    dp_can[h, a, b] = 0

    return ans


s = np.array([int(c) for c in input()], dtype=np.int8)
print(solve(s))

Solution (Python):
import numpy as np
import numba as nb


@nb.njit('(i1[:],)', cache=True)
def solve(s):
    n = len(s)
    size = n // 2
    MOD = 998244353
    dp_can = np.zeros((n + 1, size + 1, size + 1), dtype=np.int8)
    dp_cnt = np.zeros((n + 1, size + 1, size + 1), dtype=np.int64)

    dp_cnt[n, 0] = 1
    for j in range(size):
        dp_cnt[n, j + 1] = np.cumsum(dp_cnt[n, j]) % MOD

    for i in range(n - 1, -1, -1):
        if s[i] == 0:
            for j in range(size + 1):
                dp_cnt[i, j] = np.cumsum(dp_cnt[i + 1, j]) % MOD
        else:
            for k in range(size + 1):
                dp_cnt[i, :, k] = np.cumsum(dp_cnt[i + 1, :, k]) % MOD

    dp_can[0, 0, 0] = 1
    for i in range(n):
        dp_can[i + 1] |= dp_can[i]
        if s[i] == 0:
            dp_can[i + 1, 1:, :-1] |= dp_can[i, :-1, 1:]
        else:
            dp_can[i + 1, :-1, 1:] |= dp_can[i, 1:, :-1]
        if i < n - 1:
            if s[i] == 0 or s[i + 1] == 0:
                dp_can[i + 2, 1:, :] |= dp_can[i, :-1, :]
            if s[i] == 1 or s[i + 1] == 1:
                dp_can[i + 2, :, 1:] |= dp_can[i, :, :-1]
    dp_can[1:, 0, 0] = 0

    ans = 0

    for i in range(n, -1, -1):
        for j in range(size + 1):
            for k in range(size + 1):
                if dp_can[i, j, k] == 0:
                    continue

                ans = (ans + dp_cnt[i, j, k]) % MOD

                a, b = j, k
                for h in range(i - 1, -1, -1):
                    if s[h] == 0:
                        a -= 1
                    else:
                        b -= 1
                    if a < 0 or b < 0:
                        break
                    dp_can[h, a, b] = 0

    return ans


s = np.array([int(c) for c in input()], dtype=np.int8)
print(solve(s))