Harryxun/stf_run huggingface dataset:
import sys
import numpy as np

input = sys.stdin.readline
N = int(input())
B = [int(i)*2 for i in input().split()]

#a = [[0]*N for i in range(N)]
A = np.identity(N)
for i in range(N-1):
    #A[i][i] += 1
    A[i][i+1] += 1

A[-1][0] += 1
#A[-1][-1] += 1
#A = np.array(a)
b = np.array(B)

x = np.linalg.solve(A, b)

print(*x.astype(int))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
a = [int(i) for i in input().split()]

s = sum(a)
x = [None]*N
x[0] = s - 2 * (sum(a[1::2]))

for i in range(1,N):
    x[i] = 2 * a[i-1] - x[i-1]

print(*x)
N,R=map(int,input().split())
if N < 10:
  print(R+100*(10-n))
else:
  print(R)

### FIXED CODE ###

N,R=map(int,input().split())
if N < 10:
  print(R+100*(10-N))
else:
  print(R)
c = 0
while True:
    x == int(input())
    if x == 0:
        break;
    c += 1
    print('Case', str(c) = ':', x)

### FIXED CODE ###

c = 0
while True:
    x = int(input())
    if x == 0:
        break;

    c += 1
    print('Case', str(c) + ':',  x)
n,l=map(int, input().split()) #a1 a2 a3
s = [i for i in range(n)] 

s.sort()


print(''.join(s))

### FIXED CODE ###

n,l=map(int, input().split()) #a1 a2 a3

s = [input() for i in range(n)] 

s.sort()


print(''.join(s))
A = str(input())
B = str(input())
C = 0
for i in range(3):
  if A[i] == B[i]:
    C += 0
print(c)
    


### FIXED CODE ###

A = str(input())
B = str(input())
C = 0
for i in range(3):
  if A[i] == B[i]:
    C += 1
print(C)
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
dim = dp[N]
for _ in range(10**5):
    for i in src[::-1]:
        if dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break
    dim -= 1
    if dim <= 0:
        break
print(ans if ans else 0)

### FIXED CODE ###

INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i+arr[j]] = max(dp[i+arr[j]],dp[i] + 1)
dim = dp[N]
ans  = ''
while(dim > 0):
    for i in src[::-1]:
        if N >= arr[i] and dp[N-arr[i]] + 1 == dp[N]:
            ans += str(i)
            N -= arr[i]
            dim -= 1
            break
print(ans)
S=list(input())
for i in range(int(input())):
    q=input()
    if q=='1':
        S.reverse()
    else:
        a,f,c=q.split()
        S=[c]+S if f=='1' else S+[c] 
print(''.join(S))

### FIXED CODE ###

S=input()[::-1]
l=len(S)
a=1
m=10**9+7
dp=[1]+[0]*12
for d in S:
    dp2=[0]*13
    if d=='?':
        for j in range(13):
            for k in range(10):
                dp2[(j+k*a)%13]+=dp[j]%m
    else:
        for j in range(13):
            dp2[(j+int(d)*a)%13]=dp[j]
    dp=dp2
    a=(a*10)%13 if a!=1 else 10
print(dp[5]%m)
import sys
readline = sys.stdin.readline

# 0-indexでやる

D = int(readline())
C = list(map(int,readline().split())) # 満足度の下がりやすさ
S = [None] * D
sortS = [None] * D
for i in range(D):
  s = list(map(int,readline().split()))
  S[i] = s.copy()
  for j in range(len(s)):
    s[j] = (s[j],j)
  sortS[i] = sorted(s, key = lambda x:x[0], reverse = True)

def make_ans(D,C,limiter = 52, threshold = 26):
  ans = []
  last_submit = [-26] * 26
  for i in range(D):
    info = sortS[i]
    
    # 52回以上提出がないものがあれば、42回を超えたもののうちCの値が高いものを提出
    if i - min(last_submit) >= limiter:
      ind = -1
      for j in range(len(last_submit)):
        if i - last_submit[j] >= threshold:
          if ind == -1:
            ind = j
          else:
            if C[ind] < C[j]:
              ind = j
      ans += [ind]
      last_submit[ind] = i
      continue
      
    topval = info[0][0]
    for j in range(len(info)):
      val = info[j][0]
      if val < topval // 2:
        continue # 最高値の半分になるのであればやめよう
      index = info[j][1]
      if i - last_submit[index] < 26:
        continue
      ans += [index]
      last_submit[index] = i
      break
    else:
      ans += [info[0][1]]
  return ans

def calc_score(arr):
  point = 0
  last_submit = [0] * 26
  for i in range(len(arr)):
    # i日目
    point += S[i][arr[i]]
    for j in range(len(last_submit)):
      point -= (i - last_submit[j]) * C[i]
  return point
      
ans = make_ans(D,C)

best = calc_score(ans)
for limiter in range(30,53):
  for threshold in range(26, limiter):
    new_ans = make_ans(D,C,limiter,threshold)
    new_score = calc_score(new_ans)
    if new_score > best:
      print("yes",new_score,best)
      ans = new_ans
      best = new_score
  
def show(arr):
  for a in arr:
    print(a + 1)
    
show(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

D = int(readline())
C = list(map(int,readline().split()))
for i in range(D):
  S = list(map(int,readline().split()))
  
for i in range(D):
  print(1)
N, K = map(int, input().split())
price = list(map(int, input().split()))
total = price.sorted[:K]
print(total)
    

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

p.sort()
ans=0

for i in range(k):
    ans += p[i]
    
print(ans)
s=input()
t=input()
dp=[[0]*(len(t)+1) for i in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=1+dp[i-1][j-1]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=''
i=len(s)
j=len(t)
while(i>0 and j>0):
    # print(i,j,dp[i][j-1],dp[i-1][j],s[i],t[j])
    # print(ans)
    if s[i-1]==t[j-1]:
        ans=s[i]+ans
        i-=1 
        j-=1 
    else:
        if dp[i][j-1]>dp[i-1][j]:
            j-=1
            # print('here')
        else:
            i-=1 
print(ans)

### FIXED CODE ###

s=input()
t=input()
dp=[[0]*(len(t)+1) for i in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=1+dp[i-1][j-1]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=''
i=len(s)
j=len(t)
while(i>0 and j>0):
    # print(i,j,dp[i][j-1],dp[i-1][j],s[i],t[j])
    # print(ans)
    if s[i-1]==t[j-1]:
        ans=s[i-1]+ans
        i-=1 
        j-=1 
    else:
        if dp[i][j-1]>dp[i-1][j]:
            j-=1
            # print('here')
        else:
            i-=1 
print(ans)
#!/usr/bin/env python

from functools import reduce
import math

# GCD and LCM are not in math module.  They are in gmpy, but these are simple enough:

# def gcd(a,b):
#     """Compute the greatest common divisor of a and b"""
#     while b > 0:
#         a, b = b, a % b
#     return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b // math.gcd(a, b)

N = int(input())
ts = []
for _ in range(N):
  T = int(input())
  ts.append(T)

print(reduce(lcm, ts))


### FIXED CODE ###

#!/usr/bin/env python

from functools import reduce
import math

# GCD and LCM are not in math module.  They are in gmpy, but these are simple enough:

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b // gcd(a, b)

N = int(input())
ts = []
for _ in range(N):
  T = int(input())
  ts.append(T)

# print(reduce(lcm, ts))
ans = 1
for i in range(N):
  ans = lcm(ans, ts[i])
print(ans)
import sys
input=lambda: sys.stdin.readline().rstrip()
n,q=map(int,input().split())
C=[int(i) for i in input().split()]
LR=[]
for i in range(q):
    l,r=map(int,input().split())
    LR.append((i,l,r))
LR.sort(key=lambda x:x[2])


LST=[0]*n
Ans=[0]*q

n_max=5*10**5+1
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)

def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
cur=0
for i,l,r in LR:
    while cur<r:
        if LST[C[cur]]!=0:
            bitadd(BIT,LST[C[cur]],-1)
        LST[C[cur]]=cur+1
        bitadd(BIT,LST[C[cur]],1)
        cur+=1
    if l==1:
        Ans[i]=bitsum(BIT,r+1)
    else:
        Ans[i]=bitsum(BIT,r+1)-bitsum(BIT,l-1)
for ans in Ans:
    print(ans)

### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
n,q=map(int,input().split())
C=[int(i) for i in input().split()]
LR=[]
for i in range(q):
    l,r=map(int,input().split())
    LR.append((i,l,r))
LR.sort(key=lambda x:x[2])


LST=[0]*(n+1)
Ans=[0]*q

n_max=5*10**5+1
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)

def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
cur=0
for i,l,r in LR:
    while cur<r:
        if LST[C[cur]]!=0:
            bitadd(BIT,LST[C[cur]],-1)
        LST[C[cur]]=cur+1
        bitadd(BIT,LST[C[cur]],1)
        cur+=1
    if l==1:
        Ans[i]=bitsum(BIT,r+1)
    else:
        Ans[i]=bitsum(BIT,r+1)-bitsum(BIT,l-1)
for ans in Ans:
    print(ans)
n=int(input())
if n<105:
  print(0)
else:
  c=0
  for i in range(105,n+1,2):
    p=0
    for j in range(1,i//2+1,2):
      if i%j==0:
        p+=1
    if p==7:
      c+=1
print(c)
    

### FIXED CODE ###

n=int(input())
if n<105:
  print(0)
  exit()
else:
  c=0
  for i in range(105,n+1,2):
    p=0
    for j in range(1,i//2+1,2):
      if i%j==0:
        p+=1
    if p==7:
      c+=1
print(c)
n = int(input())
a = 0
b = 0

for i in range(1, n+1):
    if n%i = 0:
        if a == n/i:
            b = i
        else:
            a = i

print(a+b-2)

### FIXED CODE ###

import sys
import math

n = int(input())
ans = 0

for i in range(int(math.sqrt(n)), 0, -1):
    if n%i is 0:
        ans = int(n/i + i - 2)
        break
if ans is not 0:
    print(ans)
else:
    print(n-1)
r, D, a = map(int, input().split())

old = a
for i in range(10):
  	print(r * old - D)
    old = r * old - D

### FIXED CODE ###

r, D, a = map(int, input().split())
 
old = a
for i in range(10):
  print(r * old - D)
  old = r * old - D
N=int(input())
H=list(map(int, input().split()))
for i in range(N-1):
    A=H[i+1]
    B=H[i]-1
    if A < B:
        print(No)
    else:
        print(Yes)

### FIXED CODE ###

N=int(input())
H=list(map(int, input().split()))
Z=0
count=0
for i in range(N-1):
    A=H[i+1]
    B=H[i]-1
    if A < B:
        print('No')
        Z=Z+1
        break
    if A == B:
        count=count+1
        if count >=2 and A < C:
            print('No')
            Z=Z+1
            break
        else:
            C=A
if Z == 0:
    print('Yes')
A = int(input())
B = int(input())
if B % A == 0:
  print(A + B)
else:
  print(A - B)

### FIXED CODE ###

A, B = map(int, input().split())
if B % A == 0:
  print(A + B)
else:
  print(B - A)
import sys
input = sys.stdin.readline
def main():
    S = input().rstrip()
    CNT = 0
    ans = 0
    for c in S:
        if c == 'R':
            CNT += 1
        else:
            ans = max(ans,CNT)
            CNT = 0
    print(ans)


if __name__ == '__main__':
    main)

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    S = input().rstrip()
    CNT = 0
    ans = 0
    for c in S:
        if c == 'R':
            CNT += 1
        else:
            ans = max(ans,CNT)
            CNT = 0

    ans = max(ans,CNT)
    print(ans)


if __name__ == '__main__':
    main()
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = list(map(int, sys.stdin.readline().split()))

if K % 2 == 1:
    print(0)
    exit()

# 解説AC
# dp[i][j][k]: i まで決まってて、保留の数が j、確定した奇妙さが k
dp = np.zeros((N, N, K + 1), dtype=int)
dp[0][0][0] = 1
dp[0][1][2] = 1
for i, j, k in itertools.product(range(1, N), range(N - 1), range(K + 1)):
    if k - j * 2 < 0:
        continue
    # i == pi
    # 保留の数はそのまま
    # 奇妙さは保留の数だけ増える
    dp[i][j][k] += dp[i - 1][j][k - j * 2] * 1
    # i == p_j または j == p_i (j < i)
    # 保留の数はそのまま
    # 奇妙さは保留の数だけ増える
    # パターン数はうさぎの保留数j + かめの保留数j
    dp[i][j][k] += dp[i - 1][j][k - j * 2] * (j * 2)
    # i == p_j かつ j == p_j (j < i)
    # 保留数が1減る
    # パターン数はうさぎの保留数j * かめの保留数j
    dp[i][j][k] += dp[i - 1][j + 1][k - j * 2] * (j + 1) ** 2
    if j - 1 >= 0:
        # 両方保留
        # そのまま増やす
        dp[i][j][k] += dp[i - 1][j - 1][k - j * 2]

    dp[i][j][k] %= MOD
print(dp[-1][0][K])


### FIXED CODE ###

import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = list(map(int, sys.stdin.readline().split()))

if K % 2 == 1:
    print(0)
    exit()
if N == 1:
    if K == 0:
        print(1)
    else:
        print(0)
    exit()
if K == 0:
    print(1)
    exit()

# 解説AC
# dp[i][j][k]: i まで決まってて、保留の数が j、確定した奇妙さが k
dp = [[[0] * (K + 1) for _ in range(N)] for _ in range(N)]
dp[0][0][0] = 1
dp[0][1][2] = 1
for i, j, k in itertools.product(range(1, N), range(N - 1), range(K + 1)):
    if k - j * 2 < 0:
        continue
    # i == pi
    # 保留の数はそのまま
    # 奇妙さは保留の数だけ増える
    dp[i][j][k] += dp[i - 1][j][k - j * 2] * 1
    # i == p_j または j == p_i (j < i)
    # 保留の数はそのまま
    # 奇妙さは保留の数だけ増える
    # パターン数はうさぎの保留数j + かめの保留数j
    dp[i][j][k] += dp[i - 1][j][k - j * 2] * (j * 2)
    # i == p_j かつ j == p_j (j < i)
    # 保留数が1減る
    # パターン数はうさぎの保留数j * かめの保留数j
    dp[i][j][k] += dp[i - 1][j + 1][k - j * 2] * (j + 1) ** 2
    if j - 1 >= 0:
        # 両方保留
        # そのまま増やす
        dp[i][j][k] += dp[i - 1][j - 1][k - j * 2]

    dp[i][j][k] %= MOD
print(dp[-1][0][K])
# 標準入力
A,B,H,M=map(int,input().split())

# 角度の差が出る
A_RAD = float((H*60+M)/720*2*math.pi)
B_RAD = float(M/60*2*math.pi)
AB_RAD = A_RAD - B_RAD

C = math.sqrt(A**2+B**2-2*A*B*math.cos(AB_RAD))

print(C)

### FIXED CODE ###


import math

# 標準入力
A,B,H,M=map(int,input().split())

# 角度の差が出る
A_RAD = float((H*60+M)/720*2*math.pi)
B_RAD = float(M/60*2*math.pi)
AB_RAD = A_RAD - B_RAD

C = math.sqrt(A**2+B**2-2*A*B*math.cos(AB_RAD))

print(C)
n=int(input().split())
dic={n:1}
i=1
while True:
  if n%2==0:
    n=n//2
  else:
    n=3*n+1
  i+=1
  if n in dic:
    print(i)
    break
  else:
    dic[n]=i

### FIXED CODE ###

s = int(input())

used = set()
used |= {s}
count = 1

while True:
    if s % 2 == 0: s//=2
    else:s=3*s+1
    if s in used:
        print(count+1)
        break
    else:
        used |= {s}
        count += 1
n = input()
digit = n % 10
if(digit == 3):
  print ("bon")
elif(digit == 0 and digit == 1 and digit == 6 and digit == 8):
  print ("pon")
else:
  print ("hon")


### FIXED CODE ###

ninput = input() #これはstr型
n = int(ninput) #これでint型に直す
digit = n % 10
if digit == 3:
  print('bon')
elif digit == 0 or digit == 1 or digit == 6 or digit == 8:
  print('pon')
else:
  print('hon')
import sys;


class Main:
    s = set([i.sprit() for i in sys.stdin.readlines()]);

    print(len(s));

### FIXED CODE ###




class Main:
    N = int(input());
    s = set([input() for i in range(N)]);
    print(len(s))
MOD = 10**9 + 7
N = 10**5 + 1

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

n,m,k = map(int,input().split())

p = comb(n*m-2, k-2)

ans = 0
for i in range(1,n):
    ans += i * (n-i) * m * m * p
    ans %= MOD

for i in range(1,m):
    ans += i * (m-i) * n * n * p
    ans %= MOD

print(ans)

### FIXED CODE ###

MOD = 10**9 + 7
N = 10**6 + 10

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

n,m,k = map(int,input().split())

p = comb(n*m-2, k-2)

ans = 0
for i in range(1,n):
    ans += i * (n-i) * m * m * p
    ans %= MOD

for i in range(1,m):
    ans += i * (m-i) * n * n * p
    ans %= MOD

print(ans)
# https://atcoder.jp/contests/abc044/tasks/arc060_a
# ソートしてからごちゃごちゃやればどうにかなりそう(無理でした)

'''
解説満点解法1
もしもk枚選んだとき、合計がsになる通りの数がわかったら？→s=k*Aとなる場合の数の合計をすれば良い

k枚選んだとき、合計がsになる通りの数は典型的なDP！
dp(j,k,s)... X[0:j]からk枚選んで、その合計をsにするような選び方の総数
と定義すると、
dp(j+1,k,s) = X[j]を選んだ結果sになったときの通りの数 + X[j]を選ばずにsになっている通りの数 なので
dp(j+1,k,s) = dp(j,k-1,s-X[j]) + dp(j,k,s)

あとは初期条件と境界条件と伝播条件を付け加える。
境界条件 dp(j,k,0)=0 (数枚選んで合計が0になるのはありえない)
初期条件 dp(j,0,0)=1 (ただし、0枚選んだときは1通りとなる)(s-X[j]=0のときに1通りとなってほしいという気持ちもある)

伝播条件 s-X[j]<0に関しては dp(j-1,k-1,s-X[j])が必ず0通りとなる(ありえないので)
'''

import sys
read = sys.stdin.readline
from itertools import product


def read_ints():
    return list(map(int, read().split()))


N, A = read_ints()
X = read_ints()
S = sum(X)

# 満点解法1
dp = [[[0] * (S + 1) for _ in range(N + 1)] for _ in range(N + 1)]
for j in range(N + 1):  # 初期条件
    dp[j][0][0] = 1  # 1枚も選ばずに0になるのは1通り


for j, k, s in product(range(N), range(1, N + 1), range(S + 1)):
    dp[j + 1][k][s] = dp[j][k][s] + \
        (0 if s - X[j] < 0 else dp[j][k - 1][s - X[j]])

# s=k*Aとなるような通りの数の総数
ans = 0
for k in range(1, N + 1):  # 0個はとる通りの数はいらない
    ans += dp[N][k][k * A]

# print(dp)
print(ans)


'''
満点解法2


'''


### FIXED CODE ###

# https://atcoder.jp/contests/abc044/tasks/arc060_a
# ソートしてからごちゃごちゃやればどうにかなりそう(無理でした)

'''
解説満点解法1
もしもk枚選んだとき、合計がsになる通りの数がわかったら？→s=k*Aとなる場合の数の合計をすれば良い

k枚選んだとき、合計がsになる通りの数は典型的なDP！
dp(j,k,s)... X[0:j]からk枚選んで、その合計をsにするような選び方の総数
と定義すると、
dp(j+1,k,s) = X[j]を選んだ結果sになったときの通りの数 + X[j]を選ばずにsになっている通りの数 なので
dp(j+1,k,s) = dp(j,k-1,s-X[j]) + dp(j,k,s)

あとは初期条件と境界条件と伝播条件を付け加える。
境界条件 dp(j,k,0)=0 (数枚選んで合計が0になるのはありえない)
初期条件 dp(j,0,0)=1 (ただし、0枚選んだときは1通りとなる)(s-X[j]=0のときに1通りとなってほしいという気持ちもある)

伝播条件 s-X[j]<0に関しては dp(j-1,k-1,s-X[j])が必ず0通りとなる(ありえないので)
'''

import sys
read = sys.stdin.readline
from itertools import product


def read_ints():
    return list(map(int, read().split()))


N, A = read_ints()
X = read_ints()
S = sum(X)

# 満点解法1
dp = [[[0] * (S + 1) for _ in range(N + 1)] for _ in range(N + 1)]
for j in range(N + 1):  # 初期条件
    dp[j][0][0] = 1  # 1枚も選ばずに0になるのは1通り


for j, k, s in product(range(N), range(1, N + 1), range(S + 1)):
    dp[j + 1][k][s] = dp[j][k][s] + \
        (0 if s - X[j] < 0 else dp[j][k - 1][s - X[j]])

# s=k*Aとなるような通りの数の総数
ans = 0
for k in range(1, N + 1):  # 0個はとる通りの数はいらない
    s = k * A
    if s <= S:
        ans += dp[N][k][s]

# print(dp)
print(ans)


'''
満点解法2


'''
n = input()
li = list(str(n))
li_ = [int(i) for i in li]
allSum = sum(li_)
if not n % allSum: print("Yes")
else: print("No")

### FIXED CODE ###

n = int(input())
li = list(str(n))
li_ = [int(i) for i in li]
allSum = sum(li_)
if not n % allSum: print("Yes")
else: print("No")
import sys
 
if __name__ == '__main__':
  r = int(input())
  a = r.split('\n')
  n = a[0]
  s = a[1]
  print(n)


### FIXED CODE ###

import sys
 
def exec(n, s):
  r = 'No'
  if n % 2 != 0:
    return r
  hs = s[0:int(n/2)]
  if hs + hs == s:
    r = 'Yes'
  return r
    
    
if __name__ == '__main__':
  r = [input(), input()]
  n = int(r[0])
  s = r[1]
  print(exec(n, s))
n=int(input())
r=[int(input())for _ in range(n)]
print(max([max(r[i+1:])-r[i]for i in range(min(r.remove(min(r))),n-1)]))

### FIXED CODE ###

import sys
def f():
 s=1e10;b=-s
 input()
 for r in map(int,sys.stdin):
  if b<r-s:b=r-s
  if s>r:s=r
 print(b)
f()
n, m, l = [int(i) for i in input().split()]

A = []
B = []
C = []

for ni in range(n):
    A.append([int(i) for i in input().split()])

for mi in range(m):
    B.append([int(i) for i in input().split()])

for i in range(n):
    C.append([])
    for j in range(l):
        C[i].append(0)
        for k in range(m):
            C[i][j] += A[i][k] * B[k][j]
    
for li in range(l):
    print(" ".join([str(s) for s in C[li]]))

### FIXED CODE ###

n, m, l = [int(i) for i in input().split()]

A = []
B = []
C = []

for ni in range(n):
    A.append([int(i) for i in input().split()])

for mi in range(m):
    B.append([int(i) for i in input().split()])

for i in range(n):
    C.append([])
    for j in range(l):
        C[i].append(0)
        for k in range(m):
            C[i][j] += A[i][k] * B[k][j]

for ni in range(n):
    print(" ".join([str(s) for s in C[ni]]))
from math import gcd
A, B = map(int, input().split())
max_range = int(max(A, B)**0.5)

kouyaku = [0 for _ in range(max_range+1)]
kouyaku[1] = 1


saidai_kouyaku = gcd(A,B)
print(saidai_kouyaku)
for i in range(2,max_range):
    while saidai_kouyaku%i==0:
        kouyaku[i]+=1
        saidai_kouyaku = saidai_kouyaku/i
sum_num = sum(kouyaku)
answer = 0

for i in range(len(kouyaku)):
    if kouyaku[i] > 0:
        answer += 1
print(answer)

### FIXED CODE ###

from fractions import gcd
A, B = map(int, input().split())

saidai_kouyaku = gcd(A,B)

#%%
kouyaku = [0 for _ in range(int(saidai_kouyaku**0.5)+2)]
kouyaku[1] = 1


for i in range(2,len(kouyaku)):
    while saidai_kouyaku%i==0:
        kouyaku[i]+=1
        saidai_kouyaku = saidai_kouyaku/i

answer = 0
for i in range(len(kouyaku)):
    if kouyaku[i] > 0:
        answer += 1

if saidai_kouyaku > 1:
    print(answer+1)
else:
    print(answer)
s=input()
mod=10**9+7
ans=0
dp = [[0]*15 for i in range(15)]
dp[0][0]=1
for i in range(len(s)):
    keta = len(s)-i-1
    if s[i]=='?':
        for num in range(10):
            amari = num*10**keta
            amari%=13
            for j in range(13):
                dp[i+1][(j+amari)%13]+=dp[i][j]
    else:
        amari = int(s[i])*10**keta
        amari%=13
        for j in range(13):
            dp[i+1][(j+amari)%13]+=dp[i][j]

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

### FIXED CODE ###

s=input()
mod=10**9+7
dp = [[0]*15 for i in range(100005)]
dp[0][0]=1
for i in range(len(s)):
    keta = len(s)-i-1

    if s[i]=='?':
        nums = range(10)
    else:
        nums = [int(s[i])]
    
    tmp = pow(10,keta,13)
    for num in nums:
        amari = num*tmp%13
        for j in range(13):
            dp[i+1][(j+amari)%13]+=dp[i][j]
            dp[i+1][(j+amari)%13]%=mod

print(dp[len(s)][5])
N = int(input())
A = [int(x) for x in input().split()]
mod = 10**9+7
c = 1-N%2
flag = True
di = {}
for i in A:
    if(i not in di):
        di[i]=1
    else:
        di[i]+=1
for i in range(N//2):
    if(i+c==0):
        flag &= (di[i]==1)
    else:
        flag &= (di[i*2+c]==2)
    if(not flag):
        if(N==1):
            print(1)
        else:
            print(0)
        break
else:
    print((2<<(N//2-1))%mod)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
mod = 10**9+7
c = 1-N%2
flag = True
di = {}
if(N==1):
    if(A[0]==0):
        print(1)
    else:
        print(0)
else:
    for i in A:
        if(i not in di):
            di[i]=1
        else:
            di[i]+=1
    for i in range(N//2):
        if(i+c==0):
            if(0 not in di):
                flag = False
            else:
                flag &= (di[i]==1)
        else:
            if(i*2+c not in di):
                flag = False
            else:
                flag &= (di[i*2+c]==2)
        if(not flag):
            print(0)
            break
    else:
        print((2<<(N//2-1))%mod)