Harryxun/stf_run huggingface dataset:
mport itertools
N = int(input())
a = list(map(int,input().split()))
ruiseki = list(itertools.accumulate(a))
ans = 10**100
for i in range(N-1):
    ans = min(ans,abs(sum(a[:i+1])-sum(a[i+1:])))
print(ans)

### FIXED CODE ###

import itertools
N = int(input())
a = list(map(int,input().split()))
ruiseki = list(itertools.accumulate(a))
b = sum(a)
ans = 10**100
for i in range(N-1):
    ans = min(ans,abs(ruiseki[i]*2-b))
print(ans)
n = int(input())
a = list(map(int, input().split())
if len(set(a)) == n:
         print('YES')
else:
         print('NO')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if len(set(a)) == n:
    print('YES')
else:
    print('NO')
import collections

N = int(input())
SSS = []

for i in range(N):
  SSS.append(input())
#print(N, SSS)

#print(collections.Counter(SSS).most_common())
hindo_ck = collections.Counter(SSS).most_common()

i = 1
hindo_max = list(hindo_ck[0])

if len(hindo_ck) > 1:
  del hindo_max[-1]
  while hindo_ck[i-1][1] == hindo_ck[i][1] and i < N:
    hindo_max.append(hindo_ck[i][0])
    i += 1
  hindo_max.sort()
  
  for h in hindo_max:
    print(h)
  
else:
  hindo_max = hindo_ck[0][0]
  print(hindo_max)
#print(result)



### FIXED CODE ###

import collections

N = int(input())
SSS = []

for i in range(N):
  SSS.append(input())
#print(N, SSS)

#print(collections.Counter(SSS).most_common())
hindo_ck = collections.Counter(SSS).most_common()

i = 1
hindo_max = list(hindo_ck[0])

if len(hindo_ck) > 1:
  del hindo_max[-1]
  while i < N and hindo_ck[i-1][1] == hindo_ck[i][1]:
    hindo_max.append(hindo_ck[i][0])
    i += 1
  hindo_max.sort()
  
  for h in hindo_max:
    print(h)
  
else:
  hindo_max = hindo_ck[0][0]
  print(hindo_max)
#print(result)
a,b = map(float,input().split())
ans = ((a*b*100) /100)// 1
print(int(ans))

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 1
for i in A:
    ans *= i
    ans = min(ans,10**18 + 1)
if ans >= 10**18 + 1:
    ans = -1
print(ans)
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    l = []
    for _ in range(40):
        cnt = 0
        for i in range(n):
            if a[i] & 1:
                cnt += 1
            a[i] >>= 1
        l.append(cnt)

    pows = [1]
    for _ in range(39):
        pows.append(pows[-1] * 2)

    right = 40

    def solve(k, right):
        if right == 0:
            return 0

        left = k.bit_length()
        x = 0
        y = 0
        for i in range(left):
            if l[i] < n - l[i]:
                x += pows[i]
                y += (n - l[i]) * pows[i]
            else:
                y += l[i] * pows[i]
        for i in range(left, right):
            y += l[i] * pows[i]

        if x <= k:
            return y
        else:
            return max(y - (n-2*l[right-1]) * pows[right-1], (n - l[i]) * pows[right-1] + solve(k - pows[right-1], left))

    print(solve(k, right))

main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    l = []
    for _ in range(40):
        cnt = 0
        for i in range(n):
            if a[i] & 1:
                cnt += 1
            a[i] >>= 1
        l.append(cnt)

    pows = [1]
    for _ in range(39):
        pows.append(pows[-1] * 2)

    if k == 0:
        print(sum([l[i] * pows[i] for i in range(40)]))
        exit()

    # when it does not use the biggest bit of k
    ans1 = 0
    for i in range(k.bit_length() - 1):
        if l[i] < n - l[i]:
            ans1 += (n - l[i]) * pows[i]
        else:
            ans1 += l[i] * pows[i]
    for i in range(k.bit_length() - 1, 40):
        ans1 += l[i] * pows[i]

    # when it use the biggest bit of k
    ans2 = 0
    ans3 = 0
    for i in range(40):
        if l[i] < n - l[i]:
            if k & 1:
                ans2 += (n - l[i]) * pows[i]
            else:
                ans2 += l[i] * pows[i]
            ans3 += (n - l[i]) * pows[i]
        else:
            if k & 1:
                ans2 = ans3 + l[i] * pows[i]
            else:
                ans2 += l[i] * pows[i]
            ans3 += l[i] * pows[i]
        k >>= 1

    print(max(ans1, ans2))

main()
def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list
ya=make_divisor_list(N)
answer=[]
 
lenarray=len(ya)
if lenarray%2==0:
  for i in range(lenarray//2):
    x=ya.pop(0)+ya.pop(-1)
    answer.append(x)
else:
  for i in range((lenarray-1)//2):
    x=ya.pop(0)+ya.pop(-1)
    answer.append(x)
 
 
  y=ya[0]
  answer.append(y*2)
  
print(min(answer)-2)
N=int(input())

ya = []

for i in range(1,N+1):
    if N % i == 0:
        ya.append(i)
answer=[]

lenarray=len(ya)
if lenarray%2==0:
  for i in range(lenarray//2):
    x=ya.pop(0)+ya.pop(-1)
    answer.append(x)
else:
  for i in range((lenarray-1)//2):
    x=ya.pop(0)+ya.pop(-1)
    answer.append(x)


  y=ya[0]
  answer.append(y*2)
  
print(min(answer)-2)

### FIXED CODE ###

n=int(input())
xlist=[]
 
for i in range(1,int(n**0.5)+1):
    if n%i==0:
        xlist.append(i)
 
ans=max(xlist)
print(int(ans+n/ans-2))
H, W = map(int, input().split())
a = [input()for _ in range(H)]
print("#"*(W+2))
for r in a:
    print(f"#{r}#")
print("#"*(W+2))

### FIXED CODE ###

H, W = map(int, input().split())
a = [input()for _ in range(H)]
print("#"*(W+2))
for r in a:
    print("#"+r+"#")
print("#"*(W+2))
N,K = map(int,input().split())
X = list(map(int,input().split()))

for i in range(N - K + 1):
    l = i
    r = i + K - 1

    Xl, Xr = X[l], X[r]
    if i == 0:
        ans = abs(Xl) + abs(Xr - Xl), abs(Xr) + abs(Xl - Xr)
    else:
        ans = min(abs(Xl) + abs(Xr - Xl), abs(Xr) + abs(Xl - Xr) , ans)


print(ans)


### FIXED CODE ###

N,K = map(int,input().split())
X = list(map(int,input().split()))

for i in range(N - K + 1):
    l = i
    r = i + K - 1

    Xl, Xr = X[l], X[r]
    if i == 0:
        ans = min(abs(Xl) + abs(Xr - Xl), abs(Xr) + abs(Xl - Xr))
    else:
        ans = min(abs(Xl) + abs(Xr - Xl), abs(Xr) + abs(Xl - Xr) , ans)


print(ans)
print(int(sys.argv[1]) ** 3)
print("Hello World")

### FIXED CODE ###

# -*- coding:UTF-8 -*-
print(int(input()) ** 3)
n = int(input())
h_list = [int(e) for e in input().split()]
answer = 'Yes'

for i in range(n):
    if h_list[n] <= h_list[n+1]:
        continue
    else:
        h_list[n] -= 1
        if h_list[n] > h_list[n+1]:
            answer = 'No'
            break

print(answer)

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
for i in range(n-2,-1,-1):
  if arr[i]>arr[i+1]:
    arr[i]-=1
    if arr[i]>arr[i+1]:
      print('No')
      break
else:
  print('Yes')
N= int(input())
if N%9 =0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N= int(input())
if N%9 ==0:
    print("Yes")
else:
    print("No")
import math 
import bisect
N,K=map(int,input().split())
A=[int(x) for x in input().split()]
A=sorted(A)
left=0
right=max(A)
mid=N//2
while(right-left>=1):
    numofcut=0
    mid=(left+right)//2
    for i in range(N):
        if A[i]%mid==0:
            numofcut+=A[i]//mid -1
        else:
            numofcut+=A[i]//mid
    #print(numofcut)
    if numofcut>K:
        left=mid+1
    else:
        right=mid
    

print(mid)

### FIXED CODE ###

import math 
N,K=map(int,input().split())
A=[int(x) for x in input().split()]
A=sorted(A)
left=0
right=max(A)
mid=max((left+right)//2,1)

while(right-left>=1):
    numofcut=0
    
    for i in range(N):
        if A[i]%mid==0:
            numofcut+=(A[i]//mid) -1
        else:
            numofcut+=A[i]//mid
    #print(numofcut)
    if numofcut>K:
        left=mid+1
    else:
        right=mid
    mid=max((left+right)//2,1)
    if mid==1:
        break
print(mid)
N,M,X = map(int, input().split())
a = input().split()
a += str(X) 
b = sorted(a).index(str(X))
if b <= (len(a)-1-b):
    print(b)
else:
    print(len(a)-1-b)


### FIXED CODE ###

n,m,x=map(int,input().split())
s=sum(int(i)<x for i in input().split())
print(min(s,m-s))
import collections
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


G = unionFind(N)

for a, b in AB:
    G.unite(a, b)

for i in range(N):
    G.root(i)
C = collections.Counter(G.parent).most_common()

print(C[0][1])


### FIXED CODE ###

import collections
import sys
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


G = unionFind(N)

for a, b in AB:
    G.unite(a, b)

for i in range(N):
    G.root(i)

C = collections.Counter(G.parent).most_common()

print(C[0][1])
#１行目の『N M』の取得
N,M=map(int,input().split())

#2-(M+1)行目の取得
switch_li=[[] for _ in range(M)] 
#M個の入れ子のリスト、スイッチの個数、スイッチ何がついているか
for i in range(M):
    li=list(map(int,input().split()))
    switch_li[i].extend(li)
    #appendではなくてextendを使ってリストを展開してから結合する

#スイッチの個数は正直データとして要らないので消す
#del li[0] で値消せる
for i in range(M):
    del switch_li[i][0]
#これでついているスイッチだけを格納したM列の入れ子リストができた

#M+2行目のPの取得
P=list(map(int,input().split()))

#スイッチのつき方の全探索する
#スイッチはN個あり、それが着くか付かないかで、場合の数は、2**N通り
switch_bit=[[] for _ in range(2**N)]
for i in range(2**N):
    for j in range(N):
        if (i>>j)&1==1:
            switch_bit[i].append(j+1)
        else:
            continue
#これで全ての組み合わせを抽出できた（スイッチonのものだけが記載される）

#switch_bitそれぞれについて条件を満たすのかどうか判定する
#まずスイッチ3で考えてみる(具体的でまず考えた方がわかりやすい)、その後それを一般化する
#switch_li{2}の要素をfor文で回して、スイッチonのものに含まれている場合は、リストに追加する
#それを最後に2で割って値を比べる
#まずスイッチ３のままコード書いてあとでそれを修正する
#今は何かスイッチ光っているものが入力されているとする（ここではswitch_bit[i]とする）
#実際実行することを考えると、iでスイッチ光るものを固定（switch_bit）し、j=3でスイッチを固定して光るかどうか判定する


#スイッチのつく組みが与えられている時に、電球がつくかどうか判定する関数を作る
def light_or_not(x,i):
    li=[]
    for k in switch_li[x-1]:
        if k in switch_bit[i]:
            li.append(k)
        else:
            continue
    if len(li)==0:
        return False
    elif len(li)%2==P[x-1]:
        return True
    else:
        return False
    
ans=0
for i in range(2**N):
    for j in range(1,N+2):
        if j==N+1:
            ans+=1
        elif light_or_not(j,i):
            continue
        else:
            break
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(M)]  #sの各要素のはじめはk
p = list(map(int, input().split()))
ans = 0

# 0をoffとして2進数でパターンを表現

for i in range(2 ** N):
    ptn = bin(i)[2:].rjust(N, "0")  # N桁の2進表現にする,さらに0を足している（左に）
    light = True  # 着目している電球が点灯していないときはこれがFalseになる
    for j in range(M):
        tmp = 0  # 着目している電球について、スイッチのonの個数をカウントする
        for n in range(1, s[j][0] + 1):
            if ptn[s[j][n] - 1] == "1":
                tmp += 1
        if tmp % 2 != p[j] % 2:
            light = False
    if light:
        ans += 1

print(ans)
def main():
  import itertools
  
  L,R=map(int,input().split())
  if R<45:
    print(L*(L+1))
    exit()
  elif L<=2019 and 2019<=R:
    print(0)
    exit()
  else:
    z=range(L,R+1)
    ans=float("inf")
    for i,j in itertools.combinations(z,2):
      if (i*j)%2019==0:
        print(0)
        break
      else:
        ans=min(ans,(i*j)%2019)
    else:
      print(ans)
  
if __name__=="__main__":
  main()

### FIXED CODE ###

def main():
  
  L,R=map(int,input().split())
  x,y=L//2019,R//2019
  
  if y-x>=1:
    print(0)
    
  else:
    i=R
    k=1
    ans=float("inf")
    while(L<i):
      ans=min(ans,i*(i-k)%2019)
      if ans==0:
        print(0)
        break        
      k+=1
      if i-k<L:
        k=1
        i-=1
        
    else:
      print(ans)
      
if __name__=="__main__":
  main()
def check(l, r):
    th = 1 + (r - l + 1) // 2 
    for i in range(26):
        if cnt[i] >= th:
            return True
    return False

s = input()
n = len(s)
si = [0] * n
for i in range(n):
    si[i] = ord(s[i]) - 97

l, r = 0, 2
cnt = [0]*26
for i in range(3):
    cnt[si[i]] += 1
while l < n-2 and r < n:
    # print(l, r, cnt)
    if check(l, r):
        print(l, r)
        exit()
    elif max(cnt) == (r-l) // 2:
        r += 1
        if r < n:
            cnt[si[r]] += 1
    else:
        cnt[si[l]] -= 1
        l += 1     
print(-1, -1)

### FIXED CODE ###

def check(l, r):
    th = 1 + (r - l + 1) // 2 
    for i in range(26):
        if cnt[i] >= th:
            return True
    return False

s = input()
n = len(s)
si = [0] * n
for i in range(n):
    si[i] = ord(s[i]) - 97

l, r = 0, 1
cnt = [0]*26
for i in range(2):
    cnt[si[i]] += 1
while l < n-1 and r < n:
    if check(l, r):
        print(l+1, r+1)
        exit()
    elif max(cnt) == 1 + (r - l + 1) // 2 or r-l == 1:
        r += 1
        if r < n:
            cnt[si[r]] += 1
    else:
        cnt[si[l]] -= 1
        l += 1     
print(-1, -1)
count = 1
x = input()
while x != "0":
    print("Case{}: {}".format(c, x))
    x = input()
    count += 1

### FIXED CODE ###

c = 1
x = input()
while x != "0":
    print("Case {}: {}".format(c, x))
    x = input()
    c += 1
def solve():
    N, M = map(int, input().split())
    INF = 10 ** 9
    
    dp = [INF] * (2 ** N)
    dp[0] = 0
    for _ in range(M):
        a, b = map(int, input().split())
        c = list(map(lambda x: int(x) - 1, input().split()))
        open = 0
        for i in range(b):
            open += 1 << c[i]
        for i in range(2 ** N):
            if dp[i] + a <= dp[i | open]:
                dp[i | open] = dp[i] + a
    
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# coding: utf-8


def solve():
    N = int(input())
    count = 0
    
    for i in range(1, N+1):
        if i % 2 == 1:
            count += 1
    
    print(count/N)


if __name__ == '__main__':
    solve()
n=int(input())
s=input()
r,g,b=[],[],[]
ans=0
for i in range(n):
  if s[i]=="R":
    r.append(i)
  elif s[i]=="G":
    g.append(i)
  elif s[i]=="B":
    b.append(i)
for i in range(len(r)):
  for j in range(len(g)):
    l=[r[i],g[j],b[2*j-i]]
    l.sort()
    if l[1]-l[0]!=l[2]-l[1]:
      ans+=1
print(ans)  

### FIXED CODE ###

n=int(input())
s=input()
r=s.count("R")
g=s.count("G")
b=s.count("B")
ans=r*g*b
for i in range(n):
  for j in range(i+1,n):
    if 2*j-i<n:
      if s[i]!=s[j] and s[i]!=s[2*j-i] and s[j]!=s[2*j-i]:
        ans-=1
print(ans)
s = str(input())
if RRR in s:
  print(3)
  elif RR in s:
    print(2)
    elif SSS in s:
      print(0)
      else:
        print(1)

### FIXED CODE ###

s = input()
if s == "RRR":
  print(3)
if s == "SSS":
  print(0)
if s == "RRS":
  print(2)
if s == "SRR":
  print(2)
if s == "RSS":
  print(1)
if s == "SRS":
  print(1)
if s == "SSR":
  print(1)
if s == "RSR":
  print(1)
n, q = map(int, input().split())
s = input()
flag = False
count = 0
li = [0]

for i in s:
    if i == "A":
        flag = True
    if i == "C" and flag is True:
        count += 1
        flag = False
    li.append(count)
    print(li)

for i in range(q):
    l, r = map(int, input().split())
    print(li[r] - li[l])


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
flag = False
count = 0
li = []

for i in range(n):
    if s[i] == "A":
        flag = True
    elif s[i] == "C" and flag is True:
        count += 1
        flag = False
    else:
        flag = False
    li.append(count)

for i in range(q):
    l, r = map(int, input().split())
    print(li[r-1] - li[l-1])
S = input()
n = len(S)

for i in range(int(n/2)+1):
    if S[2*i] != "R" and S[2*i] != "U" and S[2*i] != "D":
        print("No")
        exit()
for i in range(int(n/2)):
    if S[2*i + 1] != "L" and S[2*i + 1] != "U" and S[2*i + 1] != "D":
        print("No")
        exit()
print("Yes")

### FIXED CODE ###

import math
S = input()
n = len(S)

for i in range(math.ceil(n/2)):
    if S[2*i] != "R" and S[2*i] != "U" and S[2*i] != "D":
        print("No")
        exit()
for i in range(int(n/2)):
    if S[2*i + 1] != "L" and S[2*i + 1] != "U" and S[2*i + 1] != "D":
        print("No")
        exit()
print("Yes")
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    X = list(map(int, input().split()))

    if X[0] >= 0:
        print(X[k - 1])
        exit()
    elif X[-1] < 0:
        print(abs(X[-(k + 1)]))
        exit()

    for i in range(n):
        if X[i] >= 0:
            ori = i
            break

    res = f_inf
    left = max(ori - k, 0)
    right = min(ori + k, n)
    for i in range(left, right - k + 1):
        RL = abs(X[i + k - 1] - X[i]) + abs(X[i + k - 1])
        LR = abs(X[i]) + abs(X[i + k - 1] - X[i])
        res = min(res, min(RL, LR))
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

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

if x[0] >= 0:
    print(x[k - 1])
    exit()
elif x[n - 1] < 0:
    print(abs(x[n - k]))
    exit()
else:
    for i in range(n):
        if x[i] >= 0:
            ori = i
            break

f_inf = float("inf")
res = f_inf
for i in range(max(ori - k, 0), min(ori + k, n) - k + 1):
    time = min(abs(x[i + k - 1] - x[i]) + abs(x[i + k - 1]), abs(x[i]) + abs(x[i + k - 1] - x[i]))
    res = min(res, time)

print(res)
r,g,b,n = (int(i) for i in input().split())
ans = 0
for i in range(n//r+1):
    for j in range((n-(i*r))//g+1):
        #k = (n-r*i-j*g)//b
        if r*i+j*g+abs(((n-r*i-j*g)//b)*k) == n:
            ans += 1
print(ans)


### FIXED CODE ###

r,g,b,n = (int(i) for i in input().split())
ans = 0
for i in range(n//r+1):
    for j in range((n-(i*r))//g+1):
        k = (n-r*i-j*g)//b
        if r*i+j*g+abs(k*b) == n:
            ans += 1
print(ans)
x = input()
if '7' in x :
	print(Yes)
else :
	print(No)

### FIXED CODE ###

x = input()
if '7' in x :
    print('Yes')
else :
    print('No')
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

n,a = imap()
x = np.array(iarr()) - a
xsum = sum(x)

# dp[i][和 + NA]
# 本来のSの範囲は、n*(1-a)からn*(50-a)
# 負の数はdp半以外なのでNAたすと、1*nから50*N
# 和０のときは dp[n][0+NA]
dp = np.zeros((n+1, 50*n+1)).astype(int)
dp[0][n*a] = 1

for i in range(n):
    for s in range(2*n*a+1):
        print(i,s)
        dp[i+1][s] = dp[i][s] + dp[i][s-x[i]] if s-x[i]>=0 else dp[i][s]

print(dp)
ans = dp[n][n*a] - 1 #実際は初期条件の０個選ぶパターンを除外
print(ans)



### FIXED CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

n,a = imap()
x = np.array(iarr()) - a

# dp[i][和 + NA]
# 本来のSの範囲は、1N-NAから50N-NA
# 負の数はdp範囲外なのでNAたすと、1Nから50N
# 和０のときは dp[n][0+NA]
dp = np.zeros((n+1, 50*n+100)).astype(int)
dp[0][n*a] = 1

for i in range(n):
    for s in range(50*n+1):
        dp[i+1][s] = dp[i][s] + dp[i][s-x[i]] if s-x[i]>=0 else dp[i][s]

ans = dp[n][n*a] - 1 #実際は初期条件の０個選ぶパターンを除外
print(ans)
#!/usr/bin/env python3
import numpy as np
N, M, C = [int(x) for x in input().split()]
B = np.array([int(x) for x in input().split()])
A = np.array([[int(x) for x in input().split()] for _ in range(N)])

print(np.sum(A@B > -C))


### FIXED CODE ###

import numpy as np
N, M, C = [int(x) for x in input().split()]
B = np.array([int(x) for x in input().split()])
A = np.array([[int(x) for x in input().split()] for _ in range(N)])
print(np.sum(np.sum(A*B, axis=1) > -C))
N, K = map(int, input().split())

opes = [0] * (K)
for i in range(2**N):
    blue_cnt = 0
    ope_count = 0
    operating = False
    for j in range(N+1):
        bin2str = str(bin(i))
        if blue_cnt > K:
            break
        if operating and bin2str[j+2:j+4:] == 0:
            operating = False
            ope_count += 1
        elif !operating and bin2str[j+2:j+4:] == 1:
            operating = True
            blue_cnt += 1
        elif bin2str][j+2:j+4:] == 1:
            blue_cnt += 1
    if blue_cnt == K:
        opes[ope_count] += 1
for i in opes:
    print(i%100000007)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)

nCr = {}
def combination(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = combination(n-1,r) + combination(n-1,r-1)
    return nCr[(n,r)]

N, K = map(int, input().split())
for i in range(1, K+1):
	if i <= N-K+1:
		A = combination(N-K+1, i)
		P = combination(K-1, i-1)
		B = A * P
		print(B % (10**9+7))
	else:
		print(0)
x,y=input.split()
if x>y:
  print(">")
elif x<y:
  print("<")
else:
  print("=")

### FIXED CODE ###

x,y=input().split()
if x>y:
  print(">")
elif x<y:
  print("<")
else:
  print("=")
a,b=map(int,input().split())
if a>=b:
  tmp=a
  a=b
  b=tmp
return a*((10**b-1)/9)

### FIXED CODE ###

a,b=map(int,input().split())
if a>=b:
  tmp=a
  a=b
  b=tmp
print(a*((10**b-1)//9))
[a, b] = [int(x) for x in input().split()]

if a < b:
    print(a < b)
else if a > b:
    print(a > b)
else:
    print(a == b)

### FIXED CODE ###

[a, b] = [int(_) for _ in input().split()]

if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')
listofentries=input().split()
letters=[]
letters1=[]
letters2=[]
if listofentries[0]%2==1:
	return No
else:
	for letter in listofentries[1]:
    	letters.append(letters)
numbertoindex= listofentries[0]/2-1

for index in range(numbertoindex):
	letters1.append(index)
for index in range(numberofindex, listofentries[0]-1)
	letters2.append(index)
  
if letters1==letters2:
	return Yes

      


### FIXED CODE ###

n=int(raw_input())
ch=raw_input()
if ch[:n//2]==ch[n//2:]:
        print('Yes')
else:
        print('No')
x, y, z = (int(i) for i in input().split())
a,b = y,x
a,c = c,a
print(a,b,c," ")


### FIXED CODE ###

x, y, z = (int(i) for i in input().split())
a,b = y,x
a,c = z,a
print(a,b,c," ")
H, W = map(int, input().split())
h, w = map(int, input().split())
print(H*W - (H - h)(W - w))

### FIXED CODE ###

H, W = map(int, input().split())
h, w = map(int, input().split())
print((H - h)*(W - w))