Harryxun/stf_run huggingface dataset:
# Author: cr4zjh0bp
# Created: Sat Mar 14 20:41:10 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

from collections import Counter

s = ns()
n = len(s)
s = s + "$"
k = ni()

c = []
cnt = 1
for i in range(len(s) - 1):
    if s[i] == s[i + 1]:
        cnt += 1
    elif cnt > 1:
        c.append(cnt)
        cnt = 1

if len(c) == 1 and c[0] == n:
    print(n * k // 2)
elif s[0] != s[-2]:
    print(sum([x // 2 for x in c[:]]) * k)
else:
    a, b = 1, 1
    if s[0] == s[1]:
        a = c[0]
    if s[-2] == s[-3]:
        b = c[-1]
    print(sum([x // 2 for x in c[:]]) * k - (a // 2 + b // 2 - (a + b) // 2) * (k - 1))

### FIXED CODE ###

# Author: cr4zjh0bp
# Created: Sat Mar 14 20:41:10 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

from collections import Counter

s = ns()
n = len(s)
s = s + "$"
k = ni()

c = []
cnt = 1
for i in range(len(s) - 1):
    if s[i] == s[i + 1]:
        cnt += 1
    elif cnt > 1:
        c.append(cnt)
        cnt = 1

if (len(c) == 1 and c[0] == n) or n == 1:
    print(n * k // 2)
elif s[0] != s[-2]:
    print(sum([x // 2 for x in c[:]]) * k)
else:
    a, b = 1, 1
    if s[0] == s[1]:
        a = c[0]
    if s[-2] == s[-3]:
        b = c[-1]
    print(sum([x // 2 for x in c[:]]) * k - (a // 2 + b // 2 - (a + b) // 2) * (k - 1))
import sys
sys.setrecursionlimit(100000)

N = int(input())
H = list(map(int,input().split()))

def f(A):
    p = 0
    if min(A)==0 and max(A)==0:
        return 0
    if min(A)>0:
        minA = min(A)
        for i in range(len(A)):
            A[i] -= minA
        p += f(A) + minA
    else:
        for i in range(len(A)):
            if A[i]>0:
                A = A[i:]
                break
        for i in range(len(A)):
            if A[len(A)-1-i]>0:
                A = A[:len(A)-i]
                break
        x = [-1]
        for i in range(len(A)):
            if A[i]==0:
                x.append(i)
        x.append(len(A))
        for i in range(len(x)-1):
            p += f(A[x[i]+1:x[i+1]:])
    return p

print(f(H))

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))

ans = 0
st = "0"
while H!=[0]*N:
    for i in range(N):
        if H[i]>0:
            st = "+"
            H[i] -= 1
        elif st=="+" and H[i]==0:
            st = "0"
            ans += 1
    if st=="+":
        ans += 1
    st = "0"

print(ans)
n=int(input())
x=input()
s=list(x)
 
list=[]
for i in range(n):
    a=0
    l=s[:i]
    a+=l.count("W")
    k=s[i+1:]
    a+=k.count("E")
    list.append(a)
 
f=min(list)

### FIXED CODE ###

a, b= map(int, input().split())
 
c=a+b
d=a-b
e=a*b
 
f=max([c, d, e])
 
print(f)
n, m = map(int, input().split())

ss = [list(map(int, input().split())) for _ in range(n)]
p = [list(map(int, input().split())) for _ in range(n)]

INF = 10 ** 8 * 2
for s in ss:
    dist = INF
    c_point = 0
    a, b = s
    for i, v in enumerate(p):
        c, d = v
        manhattan = abs(a - c) + abs(b - d)
        if manhattan < dist:
            c_point = i + 1
            dist = manhattan
    print(c_point)


### FIXED CODE ###

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(M)]
ans = []

for i in range(N):
    index = 0
    lowest = pow(10, 8) * 4
    for j in range(M):
        dist = abs(ab[i][0] - cd[j][0]) + abs(ab[i][1] - cd[j][1])
        if lowest > dist:
            lowest = dist
            index = j
    print(index + 1)
H, W = [int(i) for i in input().split()]
A = [[]] * H
for i in range(H):
    A[i] = [int(i) for i in input().split()]

ans = []
x = -1
for i in range(H):
    x = x * (-1)
    l, r, d = (0, W, 1) if i % 2 == 0 else (W-1, -1, -1)
    for j in range(l, r, d):
        #print("i,j=",i, j)
        if A[i][j] % 2 == 0:
            continue
        if x == 1 and i == H - 1 and j == W - 1:
            continue
        if x == -1 and i == 0 and j == 0:
            continue
        
        if not(j + x < 0 or j + x >= W):
            A[i][j] = A[i][j] - 1
            A[i][j + x] = A[i][j + x] + 1
            ans.append((i, j, i, j+x))
        else :
            A[i][j] = A[i][j] - 1;
            A[i+1][j] = A[i+1][j] + 1
            ans.append((i, j, i+1, j));


print (len(ans))
for y, x, b, a in ans:
    print (y+1, x+1, b+1, a+1)
        


### FIXED CODE ###

H, W = [int(i) for i in input().split()]
A = [[]] * H
for i in range(H):
    A[i] = [int(i) for i in input().split()]

ans = []
x = -1
for i in range(H):
    x = x * (-1)
    l, r, d = (0, W, 1) if i % 2 == 0 else (W-1, -1, -1)
    for j in range(l, r, d):
        #print("i,j=",i, j)
        if A[i][j] % 2 == 0:
            continue
        if x == 1 and i == H - 1 and j == W - 1:
            continue
        if x == -1 and i == H - 1 and j == 0:
            continue
        
        if not(j + x < 0 or j + x >= W):
            A[i][j] = A[i][j] - 1
            A[i][j + x] = A[i][j + x] + 1
            ans.append((i, j, i, j+x))
        else :
            A[i][j] = A[i][j] - 1;
            A[i+1][j] = A[i+1][j] + 1
            ans.append((i, j, i+1, j));


print (len(ans))
for y, x, b, a in ans:
    print (y+1, x+1, b+1, a+1)
def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    
    if len(tree_dic) == 0:  #   これなしでいい？
        return ans
    tmp_lst = tree_dic[current_node][:]
    for next_node in tmp_lst:
        if next_node not in tree_dic[current_node]:#   これなしでいい？
#            print("second time")
            continue    #   深さ優先探索の過程ですでに通ったノードをもう一度通ろうとしたとき
        else:

            c = c_lst.pop()
            ans += c
            ans_lst[next_node - 1] = c

            tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
            tree_dic[next_node].remove(current_node)
            if len(tree_dic[current_node]) == 0:
                del tree_dic[current_node]#   探索し終えたノードの削除
            if len(tree_dic[next_node]) == 0:
                del tree_dic[next_node]#   探索し終えたノードの削除
    #                print()
                
            else:   #   次のノードにつながっている辺があるとき
                ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)



    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)



### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)

def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    next_node_lst = tree_dic[current_node][:]

    for next_node in next_node_lst:
        c = c_lst.pop()
        ans += c
        ans_lst[next_node - 1] = c

        tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
        tree_dic[next_node].remove(current_node)

        if len(tree_dic[current_node]) == 0:
            del tree_dic[current_node]#   探索し終えたノードの削除
        if len(tree_dic[next_node]) == 0:
            del tree_dic[next_node]#   探索し終えたノードの削除
        else:   #   次のノードにつながっている辺があるとき
            ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)
n,m=map(int,input().split())
l=1
r=n
for i in range(m):
  li,ri=map(int,input().split())
  l = max(l,li)
  r = min(r,ri)
print(max(r-l,0)

### FIXED CODE ###

n,m=map(int,input().split())
l=1
r=n
for i in range(m):
  li,ri=map(int,input().split())
  l = max(l,li)
  r = min(r,ri)
print(max(r-l+1,0))
A,B,C,D = map(int, input())
print("Yes" if C//B <= A//D else "No")

### FIXED CODE ###

A,B,C,D = map(int, input().split())
print("Yes" if (C-1)//B <= (A-1)//D else "No")
L,R= map(int,input().split())
#境界条件
bool = True
l = L % 2019
r = R % 2019
if l == 0 or r == 0:
    ans = 0
else:
    for i in range(l,r):
        for j in range(i+1,r+1):
            temp = (i * j) % 2019
            if bool:
                min = temp
                ans = min
                bool = False
            elif min > temp:
                min = temp
                ans = min
print(ans)

### FIXED CODE ###

L,R= map(int,input().split())
#境界条件
bool = True
flag = False
for i in range(L,R):
    for j in range(i+1,R+1):
        temp = (i * j) % 2019
        if bool:
            min = temp
            ans = min
            bool = False
        elif min > temp:
            min = temp
            ans = min
        if min == 0:
            flag = True
            break
    if flag:
        break
print(ans)
def resolve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * m
    b = [0] * m
    s = [[-1] for j in range(n)]
    ans=0
    for i in range(m):
        a[i], b[i] = map(int, input().split())
    for i in range(m):
        s[a[i]-1].append(b[i])
        s[b[i]-1].append(a[i])
    for i in range(n):
        if len(s[i])!=1:
            for j in s[i]:
                if j!=-1:
                    if h[i]<=h[j-1]:
                        y=0
            if not y:
               ans+=1
            y=1
    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * m
    b = [0] * m
    s = [[-1] for j in range(n)]
    ans=0
    x=1
    for i in range(m):
        a[i], b[i] = map(int, input().split())
    for i in range(m):
        s[a[i]-1].append(b[i])
        s[b[i]-1].append(a[i])
    for i in range(n):
        if len(s[i])!=1:
            for j in s[i]:
                if j!=-1:
                    if h[i]<=h[j-1]:
                        x=0
        ans+=x
        x=1
    print(ans)
resolve()
import functools
import math
n=int(input())
a=list(map(int,input().split()))
gcd = functools.reduce(math.gcd, a)
print(gcd)

### FIXED CODE ###

import fractions
from functools import reduce
n=int(input())
l=list(map(int,input().split()))
print(reduce(fractions.gcd,l))
import math
a,b = map(float, input().split())
for i in range(1,11):
    if i <= b <i+1:
        c = int(i)
        d = b - i
        
e = int(a) * c
f = a * d
g = int(math.floor(f))
h = e + g
print(math.floor(h))

### FIXED CODE ###

re = input().split()
a = int(re[0])
b = re[1]

c = int(b[0])
d = int(b[2] + b[3])
e = a * c
f = a * d
g = f // 100
h = e + g
print(h)
S=[int(input()) for _ in range(5)]
T=[]
for i in range(5):
    if S[i]%10!=0:
        T.append(10-S[i]%10)
print(sum(S)+sum(T)-max(T))

### FIXED CODE ###

S=[int(input()) for _ in range(5)]
T=[]
for i in range(5):
    T.append((10-S[i])%10)
print(sum(S)+sum(T)-max(T))
import sys
str=[]
for line in sys.stdin:
    str.append(line)
s=''.join(str).lower
s=list(s)
for i in range(97, 97 + 26):
    count = 0
    for j in s:
        if chr(i) == j:
            count += 1
    print(chr(i), ':', count)


### FIXED CODE ###

a=''
while True:
    try:
        str = input().lower()
        a+=str
    except:
        break
for i in range(97, 97 + 26):
    count = 0
    for j in a:
        if chr(i) == j:
            count += 1
    print(chr(i), ':', count)
s = input()
n = len(s)
for i in range(n):
    for j in range(i,n):
        if all("ATGC".cout(c) == 1 for c in s[i:j+1]):
            ans = max(ans,j - i + 1)
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
ans = 0
for i in range(n):
    for j in range(i,n):
        if all("ATGC".count(c) == 1 for c in s[i:j+1]):
            ans = max(ans,j - i + 1)
print(ans)
n=int(input())
a=int(input())
b=int(input())
if n==1:
    print("Hello World")
elif n==2:
    ans=a+b
    print(ans)

### FIXED CODE ###

a=int(input())
if a==1:
    print('Hello World')
    exit()
b=int(input())
c=int(input())
print(b+c)
s=input()
q=int(input())
dir=True
ans=s
query=[]
for i in range(q):
  temp=input()
  if temp[0] == "1":
    dir = dir ^ True
  if temp[0] == "2":
    t,f,c = temp.split()

    if (f == "1" and dir) or (f=="2" and not dir):
      ans=c+ans
    else:
      ans=ans+c
def reverse(s):
  t=""
  for i in range(len(s)-1,-1,-1):
    t+=s[i]
  return t

if dir:
  print(ans)
else:
  print(reverse(ans))


### FIXED CODE ###

s = input()

if s.count("A") == 3 or s.count("B") == 3:
  print("No")
else:
  print("Yes")
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n = int(input())
a = [0]*n
a = list(map(int, input().split()))
map(lambda x: x-1, a)
ty=[0]*n

for i in range(0, n):
    ty[a[i]]+=1

s = 0

for i in range(0, n):
    if ty[i]>=2:
        s += comb(ty[i], 2)

for k in range(0, n):
    if ty[a[k]]==2:
        print(s-1)
    elif ty[a[k]]>2:
        print(s-comb(ty[a[k]], 2)+comb(ty[a[k]]-1, 2))
    else:
        print(s)

### FIXED CODE ###

import random


def nC2(n):
    return int(n*(n-1)/2)

n = int(input())

a = [0]*n
a = list(map(int, input().split()))
a = [i-1 for i in a]

ty=[0]*n

for i in range(0, n):
    ty[a[i]]+=1

s = 0

for i in range(0, n):
    if ty[i]>=2:
        s += nC2(ty[i])

for k in range(0, n):
    if ty[a[k]]==2:
        print(s-1)
    elif ty[a[k]]>2:
        print(s-nC2(ty[a[k]])+nC2(ty[a[k]]-1))
    else:
        print(s)
s = input()
flag = 0
for i in range(len(s)):
    if s[i] == "A":
        if s[i + 1] == "C":
            flag = 1
if flag == 1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input()
flag = 0
for i in range(len(s) - 1):
    if s[i] == "A":
        if s[i + 1] == "C":
            flag = 1
if flag == 1:
    print("Yes")
else:
    print("No")
int(input())
print(x * x * x)




### FIXED CODE ###

x =int(input())
print(x * x * x)
n,a,b=map(int, input().split())

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 = 10**9+7 
N = 10**4
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
A=cmb(n,a,mod)
B=cmb(n,b,mod)  
C=pow(2,n,mod)

if n==2:
    print(0)
else:
    print((C-1-A-B)%mod)

### FIXED CODE ###

n,a,b=map(int, input().split())
 
def comb(n, r,MOD):
    p, q = 1, 1
    for i in range(r):
        p = p * (n-i) % MOD
        q = q * (i+1) % MOD
    return p * pow(q, MOD-2, MOD) % MOD

mod=10**9+7
    
A=comb(n,a,mod)
B=comb(n,b,mod)  
C=pow(2,n,mod)

if n==2:
    print(0)
else:
    print((C-1-A-B)%mod)
def main():
    N = input()
    N = int(N)

    k = 1
    s = []
    #lst = list(range(1,N+1))
    primes = prime(N)
    num = len(primes)

    # N=1
    lst = [0] * N
    if N ==1:
        print(1)
        exit()

    # N>=2
    for i in range(2,N+1):
        b =[]
        b = bunkai(i)
        for i in b:
            lst[primes.index(i)] += 1

    ans = 1
    for i in lst:
        if i is not 0:
            ans = ans * (i+1)
    print(ans%1000000007)


def prime(n):
    primes = []
    for i in range(2,n):
        flag = True
        for j in range(2,i):
            if i%j == 0:
                flag = False
        if flag:
            primes.append(i)
    return primes

def bunkai(i):
    bunkai =[]
    s =0
    while s ==0:
        for j in range(2,i+1):
            if i % j ==0:
                bunkai.append(j)
                i = int(i/j)
                if i ==1:
                   s=1
                break
    return bunkai

if __name__ == "__main__":
        main()


### FIXED CODE ###

def main():
    N = input()
    N = int(N)

    k = 1
    s = []
    #lst = list(range(1,N+1))
    primes = prime(N+1)
    num = len(primes)

    # N=1
    lst = [0] * N
    if N ==1:
        print(1)
        exit()

    # N>=2
    for i in range(2,N+1):
        b =[]
        b = bunkai(i)
        for i in b:
            lst[primes.index(i)] += 1

    ans = 1
    for i in lst:
        if i is not 0:
            ans = ans * (i+1)
    print(ans%1000000007)


def prime(n):
    primes = []
    for i in range(2,n):
        flag = True
        for j in range(2,i):
            if i%j == 0:
                flag = False
        if flag:
            primes.append(i)
    return primes

def bunkai(i):
    bunkai =[]
    s =0
    while s ==0:
        for j in range(2,i+1):
            if i % j ==0:
                bunkai.append(j)
                i = int(i/j)
                if i ==1:
                   s=1
                break
    return bunkai

if __name__ == "__main__":
        main()
import sys

x = []
for _ in range(3):
    x.extend(list(map(int,input().split())))
a = b = c = d = 0
for i in range(6):
    if x[i] == 1:
        a += 1
    if x[i] == 2:
        b += 1
    if x[i] == 3:
        c += 1
    if x[i] == 4:
        d += 1
if a == 3:
    print("NO")
    sys.exit(1)
if b == 3:
    print("NO")
    sys.exit(1)
if c == 3:
    print("NO")
    sys.exit(1)
if d == 3:
    print("NO")
    sys.exit(1)
print("YES")

### FIXED CODE ###

x = []
f  = 1
for _ in range(3):
    x.extend(list(map(int,input().split())))
cnt = [0]*4
for i in range(6):
    cnt[x[i]-1] += 1
for a in cnt:
    if a > 2:
        f = 0
if f:
    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

# dp[i][和 + NA]
# 本来のSの範囲は、1N-NAから50N-NA
# 負の数はdp範囲外なのでNAたすと、1Nから50N
# 和０のときは dp[n][0+NA]
dp = np.zeros((n+1, 50*n+3)).astype(int) #50*n+1だめ、なんで！？？？？？？
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)




### 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)
def main():
    s = input()
    c = 0
    for i in range(len(s)-3):
        for j in range(i+3, len(s)):
            if int(s[i:j+1]) % 2019 == 0:
                c += 1

    print(c)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    sw = list(map(int, input().split()))
    print('unsafe' if sw[0] <= sw[1] else 'safe')

if __name__ == '__main__':
    main()
N = int(input())
a = sorted([int(input()) for _ in range(N)])
print(a[-1]-a[0])

### FIXED CODE ###

N = int(input())
a = map(int, input().split())
a = sorted(a)
print(a[-1]-a[0])
s = input()
ans="Good"
for i in range(4):
	if s[i]==s[i+1]:
		ans="Bad"
print(ans)

### FIXED CODE ###

s = input()

ans="Good"
for i in range(3):
	if s[i]==s[i+1]:
		ans="Bad"
print(ans)
class BisectSearch:
    def __init__(self, f, l=0, r=10**9):
        self.f = f
        self.l = l
        self.r = r
    def __call__(self, dist):
        f = self.f
        l = self.l
        r = self.r
        if dist <= f(l):
            return l
        if f(r) <= dist:
            return r
        while r-l > 1:
            n = (r+l) // 2
            if f(n) <= dist:
                l = n
            else:
                r = n
        return l

n = int(input())
def f(n):
    return (n+1)*n // 2
m = BisectSearch(f, l=1, r=10**7)(n)
m += f(m) != n
A = set(range(1, m+1))
A.remove(f(m) - n)
print(*A, sep='\n')

### FIXED CODE ###

class BisectSearch:
    def __init__(self, f, l=0, r=10**9):
        self.f = f
        self.l = l
        self.r = r
    def __call__(self, dist):
        f = self.f
        l = self.l
        r = self.r
        if dist <= f(l):
            return l
        if f(r) <= dist:
            return r
        while r-l > 1:
            n = (r+l) // 2
            if f(n) <= dist:
                l = n
            else:
                r = n
        return l

n = int(input())
def f(n):
    return (n+1)*n // 2
m = BisectSearch(f, l=1, r=10**7)(n)
m += f(m) != n
A = set()
for i in range(m, 0, -1):
  if n - i >= 0:
    A.add(i)
    n -= i
print(*A, sep='\n')
n, a, b = map(int, input().split())
ans = 0
for i in range(n):
      if a <= sum(list(map(int, list(str(i)))) <= b:
          ans += i
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
ans = 0
for i in range(1, n+1):
      if a <= sum([int(c) for c in str(i)]) <= b:
          ans += i
print(ans)