Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import math
X, Y = map(int, input().split())
MOD = 10**9 + 7

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def solve():
    a = (2*Y-X) / 3
    b = (2*X-Y) / 3
    if a.is_integer() and b.is_integer() and a >= 0 and b >= 0:
        ans = combinations_count(a+b, min(a, b))
        print(ans%MOD)
    else:
        print(0)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

from math import factorial
X, Y = map(int, input().split())
MOD = 10**9 + 7

def comb(n, r, p):
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)

    if r < 0 or n < r:
        return 0
    r = min(r, n-r)
    return fact[n] * factinv[r] * factinv[n-r] % p

def solve():
    a = (2*Y-X) / 3
    b = (2*X-Y) / 3
    if a.is_integer() and b.is_integer() and a >= 0 and b >= 0:
        ans = comb(int(a+b), int(min(a, b)), MOD)
        print(ans)
    else:
        print(0)

if __name__ == '__main__':
    solve()
### BUGGY CODE ###

num=int(input())
word=input()
alound=word.count("R")*word.count("G")*word.count("B")
for i in range(num-2):
  for j in range(i+1,num-1):
    for k in range(j+1,num):
      if k-j==j-i and word[i]!=word[j] and word[i]!=word[k] and word[k]!=word[j]:
        alound=alound-1
print(alound)

### FIXED CODE ###

num=int(input())
word=input()
alound=word.count("R")*word.count("G")*word.count("B")
for i in range(num-2):
  for j in range(i+1,num-1):
    k=2*j-i
    if k<=num-1:
      if word[i]!=word[j] and word[i]!=word[k] and word[k]!=word[j]:
        alound=alound-1
print(alound)
### BUGGY CODE ###

N,K = map(int, input().split())
A = list(map(int, input().split()))
b = 1
c = 1
a = 0
while K < N:
    for i in range(a,K):
        b *= A[i]
    for j in range(a+1,K+1):
        c *= A[j]
    if c > b:
        print("Yes")
    else:print("No")
    b=1
    c=1
    K += 1
    a += 1

### FIXED CODE ###

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

a = 0
while K < N:
    if A[a] < A[K]:
        print("Yes")
    else:print("No")
    K += 1
    a += 1
### BUGGY CODE ###

import itertools
n,c = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(c)]
C = [list(map(int,input().split())) for _ in range(n)]
mod0 = []
mod1 = []
mod2 = []
for i in range(n):
    for j in range(n):
        # indexのずれを考慮 ((i+1)+(j+1))%3が本来のmod値
        if (i+j)%3 == 1:
            mod0.append(C[i][j]-1)
        elif (i+j)%3 == 2:
            mod1.append(C[i][j]-1)
        else:
            mod2.append(C[i][j]-1)
color_range = list(range(c))
res = float('inf')
for x,y,z in itertools.permutations(color_range, 3):
    cnt = 0
    for i in range(len(mod0)):
        cnt += D[mod0[i]][x]
    for i in range(len(mod1)):
        cnt += D[mod1[i]][y]
    for i in range(len(mod2)):
        cnt += D[mod2[i]][z]
    res = min(cnt, res)
print(res)

### FIXED CODE ###

import itertools
n,c = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(c)]
C = [list(map(int,input().split())) for _ in range(n)]
mod0 = []
mod1 = []
mod2 = []
for i in range(n):
    for j in range(n):
        # indexのずれを考慮 ((i+1)+(j+1))%3が本来のmod値
        if (i+j)%3 == 1:
            mod0.append(C[i][j]-1)
        elif (i+j)%3 == 2:
            mod1.append(C[i][j]-1)
        else:
            mod2.append(C[i][j]-1)

conv_0, conv_1, conv_2 = [],[],[]
for i in range(c):
    tmp0, tmp1, tmp2 = 0,0,0
    for j in range(len(mod0)):
        tmp0 += D[mod0[j]][i]
    for j in range(len(mod1)):
        tmp1 += D[mod1[j]][i]
    for j in range(len(mod2)):
        tmp2 += D[mod2[j]][i]
    conv_0.append(tmp0)
    conv_1.append(tmp1)
    conv_2.append(tmp2)
res = float('inf')
color_range = list(range(c))
for x,y,z in itertools.permutations(color_range, 3):
    cnt = 0
    cnt = conv_0[x] + conv_1[y] + conv_2[z]
    res = min(cnt, res)
print(res)
### BUGGY CODE ###

import itertools
n=int(input())
l=list(map(int,input().split()))
c=itertools.combinations(l,3)
ans=0
for i in c:
  if 2*max(i) < i[0]+i[1]+i[2]:
    ans+=1
print(ans)

### FIXED CODE ###

from bisect import bisect_left
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n):#一番短い棒
  for j in range(i+1,n):#二番目に短い棒
    #1+2番目の棒の長さより短く、2番目に短い棒より長い棒の範囲を探す
    ans += bisect_left(l,l[i]+l[j])-(j+1)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [0]*(k+1)
for i in range(k+1):
  for a in A:
    if i-a >= 0:
      dp[i] |= ~dp[i-a]
result = dp[k]
if result:
  print("First")
else:
  print("Second")

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [-1]*(k+1)
def dfs(k):
  if dp[k] != -1:
    return dp[k]
  for a in A:
    if k-a >= 0 and dfs(k-a) == 0:
      dp[k] = 1
      return 1
  dp[k] = 0
  return 0
result = dfs(k)
if result:
  print("First")
else:
  print("Second")
### BUGGY CODE ###

# import numpy as np
import math
import sys
input = sys.stdin.readline

X = int(input())

if X == 2:
    print(X)
    sys.exit()

if X % 2 == 0:
    X += 1

while True:
    isNotPrime = False
    temp = pow(2,X-1,X)
    if temp == 1:
        for i in range(3,int(math.sqrt(X))+1,2):
            if X % i == 0:
                isNotPrime = True
            if isNotPrime:
                break
        if isNotPrime == False:
            break
    else:
        X += 2

print(X)


### FIXED CODE ###

# import numpy as np
import math
import sys
input = sys.stdin.readline

X = int(input())

if X == 2:
    print(X)
    sys.exit()

def segment_sieve(a,b):
    ass = []
    is_prime_small = [True] * (int(b**0.5)+1)
    is_prime = [True] * (b-a)
    for i in range(2,int(b**0.5)):
        if is_prime_small[i]:
            j = 2*i
            while j**2 < b:
                is_prime_small[j] = False
                j += i
            j = max(2*i,((a+i-1)//i)*i)
            while j < b:
                is_prime[j-a] = False
                j += i
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(a+i)
    if ass[0] == 1:
        del ass[0]
    return ass

list = segment_sieve(X,100004)
res = list[0]

print(res)
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
for i in range(0,m):
  b=a.index(max(a))
  a[b]=a[b]//2
print(sum(a))

### FIXED CODE ###

import heapq as hq

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

A = []
for a in [int(_) for _ in input().split()]:
    hq.heappush(A, -a)

for _ in range(m):
    t = hq.heappop(A)
    hq.heappush(A, t / 2)
print(-sum([int(a) for a in A]))
### BUGGY CODE ###

from collections import defaultdict
N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0 for i in range(Q)]
que = []
for i in range(Q):
    l, r = map(int, input().split())
    que.append((i, l, r))

Que = que.copy()

Que.sort(key=lambda x: x[-1])
point_data = defaultdict(list)

before_node = [-1 for i in range(N+1)]
for i, v in enumerate(C):
    if point_data[v]:
        before_node[i+1] = point_data[v][-1]
    point_data[v].append(i+1)

# BIT 木


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


ftree = BIT(N)
for i in range(Q):
    querie, l, r = Que[i]
    if i == 0:
        for j in range(1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    else:
        for j in range(Que[i-1][-1]+1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    ans[querie] = ftree.get(l-1, r)
for i in range(Q):
    print(ans[i])

### FIXED CODE ###

from collections import defaultdict
import sys
def input(): return sys.stdin.readline().rstrip()
N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0 for i in range(Q)]
que = []
for i in range(Q):
    l, r = map(int, input().split())
    que.append((i, l, r))

Que = que.copy()

Que.sort(key=lambda x: x[-1])
point_data = defaultdict(list)

before_node = [-1 for i in range(N+1)]
for i, v in enumerate(C):
    if point_data[v]:
        before_node[i+1] = point_data[v][-1]
    point_data[v].append(i+1)

# BIT 木


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def Sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        return self.Sum(j)-self.Sum(i-1)


ftree = BIT(N)
for i in range(Q):
    querie, l, r = Que[i]
    if i == 0:
        for j in range(1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    else:
        for j in range(Que[i-1][-1]+1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    ans[querie] = ftree.get(l, r)
    
for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

def check(S, l):
    for i in range(len(S)-l*2+1):
        x = S[i:i+l]
        if S[i+l:].find(x) != -1:
            return True
    return False


def main():
    N = int(input())
    S = input()
    lo = 0
    hi = N//2
    while lo < hi:
        mid = -(-(lo+hi)//2)
        if check(S, mid):
            lo = mid
        else:
            hi = mid - 1
    print(lo)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def check(S, l):
    idx = {}
    for i in range(len(S)-l+1):
        x = S[i:i+l]
        if x not in idx:
            idx[x] = i
        else:
            if idx[x]+l <= i:
                return True
    return False


def main():
    N = int(input())
    S = input()
    lo = 0
    hi = N//2
    while lo < hi:
        mid = -(-(lo+hi)//2)
        if check(S, mid):
            lo = mid
        else:
            hi = mid - 1
    print(lo)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = input()
Q = int(input())
c = 0
for _ in range(Q):
  q = input()
  if (q[0] == "1"):
    c += 1
  else:
    if (q[2] == "1"):
      if (c % 2 == 0):
      	s = q[4] + s
      else:
        s = s + q[4]
    else:
      if (c % 2 == 0):
      	s = s + q[4]
      else:
        s = q[4] + s
if (c % 2 == 0):
  print(s)
else:
  print(s[::-1])

### FIXED CODE ###

from collections import deque
s = deque(input())
Q = int(input())
c = 0
for _ in range(Q):
  q = input()
  if (q[0] == "1"):
    c += 1
  else:
    if (q[2] == "1"):
      if (c % 2 == 0):
        s.appendleft(q[4])
      else:
        s.append(q[4])
    else:
      if (c % 2 == 0):
        s.append(q[4])
      else:
        s.appendleft(q[4])
if (c % 2 == 0):
  print("".join(list(s)))
else:
  print("".join(list(s))[::-1])
### BUGGY CODE ###

INF = 1000000000

def solve(s,g,E,n):
  D = [0 if i == s else INF for i in range(n)]
  U = [0 for i in range(n)]
  V = [s]
  while V:
    v = V.pop(0)
    U[v] = 1
    if v == g:
      break
    for e in E[v]:
      if not U[e[0]] and D[v] + e[1] < D[e[0]]:
        D[e[0]] = D[v] + e[1]
        V.append(e[0])
    V = sorted(V,key=lambda x:D[x])
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])
  
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      a = min(lst[1],lst[2])
      b = max(lst[1],lst[2])
      if lst[0] == 0:
        solve(a - 1, b - 1, E, n)
      elif lst[0] == 1:
        E[a - 1].append([b - 1, lst[3]])
        E[b - 1].append([a - 1, lst[3]])
  except EOFError:
    break


### FIXED CODE ###

from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break
### BUGGY CODE ###

n, m = map(int, input().split())
inputs = []
dict = {}
for i in range(m):
  p, y = map(int, input().split())
  inputs.append((p, y))
  same = dict.get(p, [])
  same.append(y)
  dict[p] = same

for v in dict.values():
  v.sort()

for i in inputs:
  p = i[0]
  x = dict[p].index(i[1]) + 1
  print(str(p).zfill(6) + str(x).zfill(6))

### FIXED CODE ###

n, m = map(int, input().split())
inputs = []
for i in range(m):
  p, y = map(int, input().split())
  inputs.append([i, p, y, 0])

inputs = sorted(inputs, key = lambda i:i[2])
count = [0 for i in range(n)]
for i in inputs:
  count[i[1]-1] += 1
  i[3] = count[i[1]-1]

inputs = sorted(inputs, key = lambda i:i[0])

for i in inputs:
  print('{0[1]:06}{0[3]:06}'.format(i))
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    d={}
    c=0
    edge1=[[] for _ in range(N*(N-1)//2)]
    edge2=[[] for _ in range(N*(N-1)//2)]
    for i in range(N):
        l=list(map(lambda x: int(x)-1,input().split()))
        prev=-1
        for x in l:
            if min(i,x)*10**3+max(i,x) in d:
                if prev!=-1:
                    edge1[prev].append(d[min(i,x)*10**3+max(i,x)])
                    edge2[d[min(i,x)*10**3+max(i,x)]].append(prev)
            else:
                d[min(i,x)*10**3+max(i,x)]=c
                if prev!=-1:
                    edge1[prev].append(c)
                    edge2[c].append(prev)
                c+=1
            prev=d[min(i,x)*10**3+max(i,x)]
    queue=deque()
    days=[-1]*(N*(N-1)//2)
    for i,l in enumerate(edge2):
        if not l:
            queue.append(i)
            days[i]=1
    if queue:
        for _ in range(10**7):
            v=queue.popleft()
            for x in edge1[v]:
                if days[x]<days[v]+1:
                    days[x]=days[v]+1
                    queue.append(x)
            if not queue:
                print(max(days))
                exit()
    print(-1)
        

    

        
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=[[] for _ in range(N)]
    for i in range(N):
        A[i]=deque(list(map(lambda x: int(x)-1,input().split())))
    days=1
    c=0
    pre=[]
    tmp=[]
    for i in range(N):
        if A[i] and A[A[i][0]][0]==i:
            tmp.append(i)
            tmp.append(A[i][0])
    tmp=list(set(tmp))
    for i in tmp:
        A[i].popleft()
        c+=1
    pre=tmp
    if c<N*(N-1):
        while c<N*(N-1):
            tmp=[]
            for i in pre:
                if A[i] and A[A[i][0]][0]==i:
                    tmp.append(i)
                    tmp.append(A[i][0])
            tmp=list(set(tmp))
            for i in tmp:
                A[i].popleft()
                c+=1
            pre=tmp
            days+=1
            if days>N*(N-1)//2:
                print(-1)
                exit()
    print(days)
                
            
        
    
        
        

    

        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

line = str(input())
lines = line.split(' ')
 
n = int(lines[0])
k = int(lines[1])
 
d = list()
 
line = str(input())
lines = line.split(' ')
 
for l in lines:
    d.append(int(l))
 
ds = list()
 
for i in range(0,n):
    for len in range(1,n-i+1):
        sum = 0
        for j in range(i,i+len):
            sum += d[j]
        ds.append(sum)
 
for i in range(40,-1,-1):
    count = 0
    o = []
 
    for dss in ds:
        if dss & (1 << i) > 0 :
            count += 1
            o.append(dss)
    if count >= k :
        ds = list(o)
  
sum = ds[0]
for i in range(1,k):
    sum = sum & ds[i]
 
print(sum)

### FIXED CODE ###

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

ds = []

for i in range(0,n):
    sum = 0
    for j in range(i,n):
        sum += d[j]
        ds.append(sum)
        #print(str(sum) + " ",end='')
    #print()

ds.sort(reverse=True)

sum = 0
for i in range(40,-1,-1):
    count = 0
    o = []
    for dss in ds:
        if dss & (1 << i) > 0 :
            count += 1
            o.append(dss)

    if count >= k :
        sum += 1 << i
        ds = o

print(sum)
### BUGGY CODE ###

# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array(lr() + [0])
# logNで終了
for _ in range(min(K, 41)):
    next = np.array([0] * (N+1))
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    A = next.cumsum()

print(*A[:-1])

### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr() + [0]
# ある回数から先は全ての電球にNを足す
for _ in range(min(K, 41)):
    next = [0] * (N+1)
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    for i in range(N):
        next[i+1] += next[i]
    A = next.copy()

print(*A[:-1])
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
from collections import defaultdict
h, w, m = map(int,input().split())
row = defaultdict(int)
col = defaultdict(int)
grid = defaultdict(int)
for _ in range(m):
    x,y = map(int,input().split())
    row[x]+=1
    col[y]+=1
    grid[(x,y)]+=1

maxi = 0
for i in row:
    for j in col:
        if maxi<row[i]+col[j]:
            maxi = row[i]+col[j]
            if grid[(i,j)]:
                maxi-=1
print(maxi)

### FIXED CODE ###

from sys import stdin
input = stdin.readline
from collections import defaultdict, deque
h, w, m = map(int,input().split())
row = defaultdict(int)
col = defaultdict(int)
grid = defaultdict(int)
for _ in range(m):
    x,y = map(int,input().split())
    row[x]+=1
    col[y]+=1
    grid[(x,y)]=1


row = sorted(list(row.items()), key = lambda x: x[1], reverse = True)
col = sorted(list(col.items()), key = lambda x: x[1], reverse = True)


#print(row)
#print(col)

t = len(row)
for idx, ele in enumerate(row):
    i,j = ele
    if j!=row[0][1]:
        t = idx
        break
row = row[:t]
t = len(col)
for idx, ele in enumerate(col):
    i,j = ele
    if j!=col[0][1]:
        t = idx
        break
col = col[:t]

#print(row)
#print(col)
#print(grid)

ans = row[0][1]+col[0][1] + (-1 if grid[(row[0][0], col[0][0])] else 0)

i,j = 0,0
for r,cr in row:
    for c,cc in col:
        if not grid[(r,c)]:
            ans = cr+cc
            break
print(ans)


# dq = deque([(i,j)])
# while dq:
#     i,j = dq.popleft()
#     temp = row[i][1]+col[j][1] + (-1 if grid[(row[i][0], col[j][0])] else 0)
#     if ans<temp:
#         ans = temp
#         break
    
#     if i+1<len(row):dq.append((i+1,j))
#     if j+1<len(col):dq.append((i,j+1))

    
# print(ans)
### BUGGY CODE ###

MOD = 10**9 + 7

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


k = int(input())
s = input()
n = len(s)
ans = 0

l = k+n + 3
 
a25 = [1]
for i in range(l):
    a25.append((a25[-1] * 25) % MOD)
a26 = [1]
for i in range(l):
    a26.append((a26[-1] * 26) % MOD)

fact, inv = prepare(n+k, MOD)
for i in range(k+1):
    c25 = a25[i]
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD

    c26 = a26[k-i]
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)

### FIXED CODE ###

MOD = 10**9 + 7

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


k = int(input())
s = input()
n = len(s)
ans = 0

l = k+n + 3
 
a25 = [1]
for i in range(l):
    a25.append((a25[-1] * 25) % MOD)
a26 = [1]
for i in range(l):
    a26.append((a26[-1] * 26) % MOD)

fact, inv = prepare(n+k, MOD)
for i in range(k+1):
    c25 = a25[i]
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD

    c26 = a26[k-i]
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, list(input()))) for _ in range(H)])

ans = float('inf')
for pattern in product([0, 1], repeat=H - 1):
    # スライスで横方向への割り方を表現する
    div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [10]

    # 横方向へ割った後、各ブロックについて縦方向にホワイトチョコの数を修正
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0))

    # 縦方向にすでにK個より多いホワイトチョコが含まれている場合はどうにもならない
    if [r for r in rows if np.any(r > K)]:
        continue

    tmp_ans = 0
    counts = [0] * len(rows)
    w = 0
    while w < W:
        for r in range(len(rows)):
            counts[r] += rows[r][w]
        if any([c > K for c in counts]):
            counts = [0] * len(rows)
            w -= 1
            tmp_ans += 1
        w += 1

    # 横に割った分を加算
    tmp_ans += len(div) - 2
    ans = min(ans, tmp_ans)

print(ans)


### FIXED CODE ###

def main():
    from itertools import product
    H, W, K = map(int, input().split())
    G = [list(map(int, list(input()))) for _ in range(H)]

    ans = float('inf')
    for pattern in product([0, 1], repeat=H - 1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        rows = []
        for grid in grids:
            row = []
            for w in range(W):
                v = 0
                for h in range(len(grid)):
                    v += grid[h][w]
                row.append(v)
            rows.append(row)

        w = 0
        d = set()
        df = False
        counts = [0] * len(rows)
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]

            if [c for c in counts if c > K]:
                if w in d:
                    df = True
                    break
                d.add(w)
                tmp_ans += 1
                counts = [0] * len(rows)
            else:
                w += 1

            if df:
                break
        
        if not df:
            tmp_ans += len(div) - 2
            ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()