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

n, W = map(int, input().split())
w = [0]*n
v = [0]*n

#dp = [[None for i in range(W+1)] for j in range(n+1)]
dp = [[None]*(W+1) for j in range(n+1)]

for i in range(n):
    v1, v2 = map(int, input().split())
#    v2, v1 = map(int, input().split())
    # w.append(v1)
    # v.append(v2)
    w[i] = v1
    v[i] = v2

# i: Index (Tracing all items)
# j: Remaining weight
# Return the sum of value
def knap(i, j):
    # print("\n# i: " + str(i))
    # print("# j: " + str(j))
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
#        dp[i][j] = 0
        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        # if dp[i][j] is None:
        #     dp[i][j] = dp[i-1][j] + v[i]
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]
#    return res

print(knap(0, W))



### FIXED CODE ###

n, W = map(int, input().split())
w = [0]*(n+1)
v = [0]*(n+1)

#dp = [[None for i in range(W+1)] for j in range(n+1)]
dp = [[0 for i in range(W+1)] for j in range(n+1)]

for i in range(n):
    w[i], v[i] = map(int, input().split())

def knap(i, j):
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
       	res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]

for i in reversed(range(n)):
    for j in range(W+1):
#        res = 0
        # if i == n-1:
        #     res = 0
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])

#print(knap(0, W))
print(dp[0][W])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
ans=0
cnt0=[0]*60
cnt1=[0]*60
mod=10**9+7
tp=[0]*60
for i in range(60):
  tp[i]=(1<<i)%mod
for i in a:
  for j in range(60):
    if (i>>j)&1:
      ans+=(cnt0[j]*tp[j])
    else:
      ans+=(cnt1[j]*tp[j])
  for j in range(60):
    if (i>>j)&1:
      cnt1[j]+=1
    else:
      cnt0[j]+=1
print(ans%mod)




### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
cnt0=[0]*60
cnt1=[0]*60
mod=10**9+7
tp=[0]*60
for i in range(60):
  tp[i]=(1<<i)%mod
for i in range(60):
    x=1<<i
    one=sum(1 for j in a if j&x)
    ans+=tp[i]*one*(n-one)
print(ans%mod)
### BUGGY CODE ###

from collections import deque

n = int(input())
que = deque()

for i in range(n):
    command = input()
    if command == "deleteFirst":
        que.popleft()
    elif command == "deleteLast":
        que.pop()
    else:
        a, b = command.split()
        if a == "insert":
            que.appendleft(b)
        else:
            try:
                que.remove(b)
            except:
                pass
print(*que)

### FIXED CODE ###

import sys
from collections import deque

n = int(input())
que = deque()

for i in range(n):
    command = sys.stdin.readline()[:-1]
    if command[0] == "i":
        que.appendleft(command[7:])
    elif command[6] == " ":
        try:
            que.remove(command[7:])
        except:
            pass
    elif command[6] == "F":
        que.popleft()
    else:
        que.pop()
print(*que)
### BUGGY CODE ###

import bisect

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    N, M = mi()
    A = list(mi())
    A.sort()
    for i in range(M):
        t = A.pop()
        t = t>>1
        bisect.insort_left(A, t)
    print(sum(A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    N, M = mi()
    A = list(map(lambda x: -int(x), input().split()))
    heapq.heapify(A)
    for i in range(M):
        t = heapq.heappop(A)
        heapq.heappush(A, -(-t//2))
    print(-sum(A))

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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7



def main():
	N, P = MAP()
	S = list(map(int, list(input())))

	def power(x, y):
		if y == 0:
			return 1
		elif y == 1:
			return x
		elif y % 2 == 0:
			return power(x, int(y/2)) ** 2 % P
		else:
			return power(x, int((y-1)/2)) ** 2 * x % P

	if P == 2 or P == 5:
		ans = 0

		for i, s in enumerate(S):
			if int(s)%P == 0:
				ans += i+1
		print(ans)

	else:
		tmp = 0

		mod_cnt = [0]*P

		for i, s in enumerate(S[::-1]):
			tmp += power(10, i) * s
			mod_cnt[tmp%P] += 1
			tmp %= P
		ans = 0
		for v in mod_cnt:
			ans += v*(v-1)//2
		print(ans+mod_cnt[0])


if __name__ == '__main__':
	main()



### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N, P = MAP()
	S = list(map(int, list(input())))

	if P == 2 or P == 5:
		ans = 0

		for i, s in enumerate(S):
			if int(s)%P == 0:
				ans += i+1
		print(ans)

	else:
		tmp = 0

		mod_cnt = [0]*P

		z = 1
		for i, n in enumerate(S[::-1]):
			tmp += n*z
			z = z * 10 % P
			mod_cnt[int(tmp)%P] += 1
		ans = 0
		for v in mod_cnt:
			ans += v*(v-1)//2
		print(ans+mod_cnt[0])


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

class BIT:
    def __init__(self, a, func=int.__add__, one=0):
        self.n = len(a)
        self.func = func
        self.one = one
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.func(self.a[i], x)
            i += i & (-i)

    def get(self, i):
        s = self.one
        i += 1
        while i != 0:
            s = self.func(s, self.a[i])
            i -= i & (-i)
        return s


n, q = map(int, input().split())
c = [int(i)-1 for i in input().split()]
que = [[i, [int(i)-1 for i in input().split()], 0] for i in range(q)]
que.sort(key=lambda x: x[1][1])
last = [-1] * n
bit = BIT([0]*(n+100))
j = 0
for i in range(n):
    if last[c[i]] != -1:
        bit.update(last[c[i]]+10, -1)
    bit.update(i+10, 1)
    last[c[i]] = i
    while j < q and que[j][1][1] == i:
        que[j][2] = bit.get(i+10) - bit.get(que[j][1][0]+9)
        j += 1
que.sort()
for i in que:
    print(i[-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline


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

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.a[i] + x
            i += i & (-i)

    def get(self, i):
        s = 0
        i += 1
        while i != 0:
            s = s + self.a[i]
            i -= i & (-i)
        return s


def inmin(x):
    return int(x)-1


if __name__ == "__main__":
    n, q = map(int, input().split())
    c = list(map(inmin, input().split()))
    que = [[i, list(map(inmin, input().split()))] for i in range(q)]
    que.sort(key=lambda x: x[1][1])
    ans = [0] * q

    last = [-1] * n
    bit = BIT([0]*(n+10))
    j = 0
    for i in range(n):
        if last[c[i]] >= 0:
            bit.update(last[c[i]]+5, -1)
        bit.update(i+5, 1)
        last[c[i]] = i
        while j < q and que[j][1][1] == i:
            ans[que[j][0]] = bit.get(i+5) - bit.get(que[j][1][0]+4)
            j += 1
    print(*ans)
### BUGGY CODE ###

n, m = map(int, input().split())
l, r = [0]*m, [0]*m
for i in range(m):
    l[i], r[i] = map(int, input().split())

ans = [0]*n
for i in range(m):
    memo = [0]*n
    for j in range(l[i]-1, r[i]):
        memo[j] = 1        
    for k in range(n):
        ans[k] += memo[k]

print(ans.count(m))

### FIXED CODE ###

n, m = map(int, input().split())
l, r = [0]*m, [0]*m
for i in range(m):
    l[i], r[i] = map(int, input().split())

ll = max(l)
rr = min(r)
if rr-ll >= 0:
    print(rr-ll+1)
else:
    print(0)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

axor=[0]*n
bxor=[0]*n

for i in range(n-1):
    axor[i] = a[i] ^ a[i+1]
    bxor[i] = b[i] ^ b[i+1]

axor[-1] = a[0] ^ a[-1]
bxor[-1] = b[0] ^ b[-1]

def MP(it):
    n = len(it)
    res = [0]*(n+1)
    res[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and it[i] != it[j]:
            j = res[j]
        j += 1
        res[i+1] = j
    return res

mp = MP(bxor)
for i in range(1,len(mp)):
    mp[i] = i - mp[i]
txt = axor + axor
head = 0
ans = list()
while head < n:
    for i in range(n):
        if bxor[i] != txt[head+i]:
            head += mp[i+1]
            break
    else:
        x = b[0] ^ a[head]
        ans.append([head, x])
        head += mp[i+1]

for k,x in ans:
    print(k,x)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

axor=[0]*n
bxor=[0]*n

for i in range(n-1):
    axor[i] = a[i] ^ a[i+1]
    bxor[i] = b[i] ^ b[i+1]

axor[-1] = a[0] ^ a[-1]
bxor[-1] = b[0] ^ b[-1]

def MP(it):
    n = len(it)
    res = [0]*(n+1)
    res[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and it[i] != it[j]:
            j = res[j]
        j += 1
        res[i+1] = j
    return res

mp = MP(bxor)
shift = [1]*(n+1)
for i in range(n):
    shift[i+1] = i+1 - mp[i+1]
txt = axor + axor
head = 0
ans = list()
start = 0
while head < n:
    for i in range(start,n):
        if bxor[i] != txt[head+i]:     
            start = max(0,i - shift[i])
            head += shift[i]
            break
    else:
        x = b[0] ^ a[head]
        ans.append([head, x])
        start = i+1 - shift[i+1]
        head += shift[i+1]


for k,x in ans:
    print(k,x)
### BUGGY CODE ###

import math
inf=float('inf')
N = int(input())
x = list(map(int, input().split()))
y = []
flg=0
for i in range(N):
    if flg==0:
        y.append(x[i])
        flg=1
        continue
    if flg==1:
        y.insert(0,x[i])
        flg=0
        continue
 
if flg==1:
    y.reverse()
 
for i in range(len(y)):
    print(y[i],end=' ')
 
quit()

### FIXED CODE ###

import math
inf=float('inf')
N = int(input())
x = list(map(int, input().split()))
y = [0]*(N)
j=0
for i in range(0,N,1):
    
    if i%2==0:
        y[j]=x[N-1-i]
  
    if i%2==1:
        y[N-1-j]=x[N-1-i]
        j+=1
    
    


for i in range(len(y)):
    print(y[i],end=' ')
 
quit()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)

def f(x):
    memo = {}
    if x == 0:
        return True
    elif x < 0:
        return False
    elif x in memo.keys():
        return f(memo[x])
    for i in range(6):
        if f(x-100-i):
            memo[x] = True
            return True
    return False

def main():
    X = int(input())
    print(int(f(X)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3

def solve(x):
    if x >= 2000:
        return True
    memo = [True] + [False]*x

    def dp(k):
        if k == 0:
            return True
        for i in range(100,106):
            if k-i >= 0 and memo[k-i]:
                return True
        
        return False
    
    for i in range(x):
        memo[i+1] = dp(i+1)
    return memo[x]



def main():
    X = int(input())
    print(int(solve(X)))
    return

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

#ABC120C-Unification.py

from sys import stdin

input = stdin.readline

S = input()

Nblock = 0

while '0' in S and '1' in S:
    for i in range(len(S)-1):
        if S[i:i+1] != S[i+1:i+2]:
            Nblock += 2
            S = S[:i] + S[i+2:]
            break

print(Nblock)


### FIXED CODE ###

#ABC120C-Unification.py

from sys import stdin

input = stdin.readline

S = input().rstrip()

Nblock = min(S.count('1'), S.count('0'))

print(Nblock*2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import itertools

N, M = map(int, input().split())

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac


mod = M % N
div = M // N
if mod == 0:
    print(M//N)
    exit()

f = primes(M)

# 素数の場合などは１
if len(f) <= 1:
    print(1)
    exit()

ans_list = []
for i in range(1,len(f)):
    set1 = set([tuple(sorted(l)) for l in list(itertools.combinations(f, i))])
    for com in set1:
        tmp = 1
        for c in com:
            tmp *= c
        if tmp >= N:
            ans_list.append(M//tmp)

if len(ans_list) == 0:
    print(1)
else:
    print(max(ans_list))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import itertools
from collections import Counter

N, M = map(int, input().split())

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac


mod = M % N
div = M // N
if mod == 0:
    print(M//N)
    exit()

f = primes(M)

# 素数の場合などは１
if len(f) == 1:
    print(1)
    exit()

cnt = Counter(f)
ans_list = []

tmp_list = []
for k,v in cnt.items():
  tmp_list.append([i for i in range(v+1)])

# print(cnt)
# print(list(itertools.product(*tmp_list)))
for p in itertools.product(*tmp_list):
    tmp = 1
    for k,i in zip(cnt.keys(),p):
        tmp = tmp * (k ** i)

    if tmp > N:
        ans_list.append(M//tmp)

if len(ans_list) == 0:
    print(1)
else:
    print(max(ans_list))
### BUGGY CODE ###

import sys
inf = sys.maxsize

n = int(input())
l = len(str(n))
m = [int(str(n)[i]) for i in range(l)]

'''
a = []
for i in range(l):
    if m[i] <= 5:
        a.append(0)
    elif m[i] > 5:
        a.append(1)

for i in range(l):
    if i < l-1 and a[i+1] == 1 and m[i] == 5:
        a[i] = 1

p = []
for i in range(l):
    if a[i] == 0:
        if i < l-1 and a[i+1] == 1:
            p.append(m[i]+1)
        else:
            p.append(m[i])
    elif a[i] == 1:
        p.append(0)

pp = ''
for i in range(l):
    pp += str(p[i])
if pp[0] == '0':
    pp = '1' + pp
pp = int(pp)
oo = pp - n
print(pp)
print(oo)
ppp = [int(str(pp)[i]) for i in range(len(str(pp)))]
ooo = [int(str(oo)[i]) for i in range(len(str(oo)))]

print(sum(ppp) + sum(ooo))
'''
dp = [0, 1] #dp[0]: ちょうど dp[1]: 1多い

for i in m:
    dp0 = dp[0]
    dp1 = dp[1]
    dp[0] = min(dp0 + i, dp1 + (10 - i))
    dp[1] = min(dp0 + i + 1, dp1 + (10 - i) - 1)
print(dp[0])


### FIXED CODE ###

#import sys
#inf = sys.maxsize

n = str(input())
#l = len(str(n))

'''
a = []
for i in range(l):
    if m[i] <= 5:
        a.append(0)
    elif m[i] > 5:
        a.append(1)

for i in range(l):
    if i < l-1 and a[i+1] == 1 and m[i] == 5:
        a[i] = 1

p = []
for i in range(l):
    if a[i] == 0:
        if i < l-1 and a[i+1] == 1:
            p.append(m[i]+1)
        else:
            p.append(m[i])
    elif a[i] == 1:
        p.append(0)

pp = ''
for i in range(l):
    pp += str(p[i])
if pp[0] == '0':
    pp = '1' + pp
pp = int(pp)
oo = pp - n
print(pp)
print(oo)
ppp = [int(str(pp)[i]) for i in range(len(str(pp)))]
ooo = [int(str(oo)[i]) for i in range(len(str(oo)))]

print(sum(ppp) + sum(ooo))
'''
dp = [0, 1] #dp[0]: ちょうど dp[1]: 1多い

for i in n:
    i = int(i)
    dp0 = dp[0]
    dp1 = dp[1]
    dp[0] = min(dp0 + i, dp1 + (10 - i))
    dp[1] = min(dp0 + i + 1, dp1 + (10 - i) - 1)
print(dp[0])
### BUGGY CODE ###

s=input()
K=int(input())

N=len(s)
L=[]
for i in range(N):
    for j in range(i,N):
        L.append(s[i:j+1])
L=sorted(list(set(L)))
print(L[K-1])

### FIXED CODE ###

s=input()
K=int(input())
abc=list("abcdefghijklmnopqrstuvwxyz")

N=len(s)
L=[]
flag=False
for a in abc:
    for i in range(N):
        if s[i]==a:
            L.append(s[i:])
            
    if flag:
        break
L=sorted(L)
#print(L)
ans=[]
for l in L:
    n=len(l)
    for i in range(n):
        t=l[:i+1]
        if t not in ans:
            ans.append(l[:i+1])
    if len(ans)>=K:
        break
#print(ans)
print(ans[K-1])
### BUGGY CODE ###

#coding:utf-8



def main():
    
    def dbg(*something):
        if DEBUG:
            print(*something)


    #正の宝石を戻すことはない
    #負の宝石を戻すのは後半
    from sys import stdin
    from math import ceil,floor
    DEBUG = False
    N,K = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))


    #残りk回のとき深さk以下の場所に正の宝石がない→終了
    #i回の操作で取れる石>それまでにとるi-1個の石の和
    #深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
    '''
    '''




    def tansaku(left,right,rK,N,score):
        dbg(V[left:right+1],rK,N,score)

        N.sort()
        max_v = score + sum(N[rK:])
        


        # n = []
        for i in range(left,min(rK+left, ceil((right - left +1)/2)+left)):
            
            if V[i] <= 0:
                #n.append(V[i])
                continue


            next_rK = rK - 1 - (i - left)
            next_tmp_v = tansaku(i+1,right,  next_rK, N+V[left:i], score+V[i])
            #next_tmp_v = tansaku(i+1,right,  next_rK, newN, score+V[i])
            max_v = max(next_tmp_v , max_v)


            break

        # n = []
        for i in range(right ,max(right - ceil((right-left+1)/2)  ,right-rK)  ,-1 ):
            
            if V[i] <= 0:
                #n.append(V[i])
                continue

            #next_V = V[:i]
            next_rK = rK - 1 - (right - i)
            #next_tmp_v = tansaku(   left,   i- left -1  ,next_rK,N+n,score+V[i])
            next_tmp_v = tansaku(   left,   i-1  ,next_rK,N+V[i+1:right+1],score+V[i])
            max_v = max(next_tmp_v , max_v)
            break


        return max_v

    print(tansaku(0,len(V)-1,K,[],0))





if __name__ == '__main__':
    main()


### FIXED CODE ###

#coding:utf-8



def main():
    
    def dbg(*something):
        if DEBUG:
            print(*something)


    #正の宝石を戻すことはない
    #負の宝石を戻すのは後半
    from sys import stdin
    from math import ceil,floor
    DEBUG = False
    N,K = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))
    
    max_value = 0
    dbg([i for i in range(3,-1,-1)])
    for getnum in range(1,min(N+1,K+1)):  #取る宝石の総数
        for a in range(getnum + 1):  #左から石を取る回数
            J = [0] * getnum #石
            b = getnum - a #右から石を取る回数
            for i in range(a):
                J[i] = V[i]
            for i in range(b):
                J[a+i] = V[-i-1]
            J.sort()
            #dbg(J,a,b)
            t = min(K-getnum,getnum) #捨てる石
           
            for i in range(t): 
                if J[i] >= 0:
                    t = i
                    break
            #dbg(J,i,t,a,b,J[t:])
            tmp_max = sum(J[t:])

            max_value = max(max_value,tmp_max)
    print(max_value)



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

n=int(input())
a=[0]*n
for i in range(n):
    a[i]=int(input())
for i in range(n):
    a[i]*=-1
    print(max(a))
    a[i]*=-1

### FIXED CODE ###

n=int(input())
a=[0]*n
for i in range(n):
    a[i]=int(input())
b=sorted(a)
for i in range(n):
    if a[i]==b[-1]:
        print(b[-2])
    else:
        print(b[-1])
### BUGGY CODE ###

H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])

### FIXED CODE ###

H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])
### BUGGY CODE ###

import math
import sys
import collections


mod = 1000000007
sys.setrecursionlimit(mod)
fact = {1: 1}


def run(n, m):
    # print('{}を{}個の数列で表現'.format(m, n))
    ans = 1
    primes = []
    for i in range(2, m):
        if m == 1:
            break
        if m % i == 0:
            cnt = 0
            while m % i == 0:
                cnt += 1
                m //= i
                primes.append(i)
            # ans *= comb(cnt+n-1, n-1)
            # ans %= mod
    counts = collections.Counter(primes)
    # print(counts)
    for (_, v) in counts.items():
        ans *= comb(v+n-1, n-1)
        ans %= mod
    return ans


def comb(n, r):
    mul = math.factorial(n) // math.factorial(n - r)
    div = math.factorial(r)
    # mul = factorial(n) // factorial(n - r)
    # div = factorial(r)
    mul %= mod
    div %= mod
    return (mul * modpow(div, (mod-2))) % mod


'''
def factorial(n):
    if n in fact:
        return fact[n]
    else:
        fact[n] = n*factorial(n-1)
        return fact[n]
'''


def modpow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        halfp = p // 2
        half = modpow(a, halfp)
        return int((half * half) % mod)
    else:
        return int((a * modpow(a, p-1)) % mod)


def main():
    n, m = map(int, input().split())
    print(run(n, m))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import sys
import collections


mod = 1000000007
sys.setrecursionlimit(mod)
fact = {1: 1}


def run(n, m):
    # print('{}を{}個の数列で表現'.format(m, n))
    ans = 1
    primes = []
    for i in range(2, m):
        if m == 1:
            break
        if i*i > m:
            break
        if m % i == 0:
            cnt = 0
            while m % i == 0:
                cnt += 1
                m //= i
                primes.append(i)
            ans *= comb(cnt+n-1, n-1)
            ans %= mod
    # counts = collections.Counter(primes)
    # print(counts)
    # for (_, v) in counts.items():
    #     ans *= comb(v+n-1, n-1)
    #     ans %= mod
    if m != 1:
        ans *= n
        ans %= mod
    return ans


def comb(n, r):
    if r > (n-r):
        r = n-r
    mul = 1
    div = 1
    for i in range(r):
        mul *= n-i
        div *= i+1
        mul %= mod
        div %= mod
    # mul = math.factorial(n) // math.factorial(n - r)
    # div = math.factorial(r)
    # mul = factorial(n) // factorial(n - r)
    # div = factorial(r)
    mul %= mod
    div %= mod
    return (mul * modpow(div, (mod-2))) % mod


'''
def factorial(n):
    if n in fact:
        return fact[n]
    else:
        fact[n] = n*factorial(n-1)
        return fact[n]
'''


def modpow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        halfp = p // 2
        half = modpow(a, halfp)
        return int((half * half) % mod)
    else:
        return int((a * modpow(a, p-1)) % mod)


def main():
    n, m = map(int, input().split())
    print(run(n, m))


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

from collections import Counter
import itertools

def verify_anagrams(first_word, second_word):
    return Counter(first_word) == Counter(second_word)

N = int(input())
S = [str(Counter(sorted(input()))) for _ in range(N)]
print(sum((x * (x - 1)) // 2 for x in Counter(S).values()))

### FIXED CODE ###

from collections import Counter
import itertools

N = int(input())
S = ["".join(sorted(input())) for _ in range(N)]
print(sum((x * (x - 1)) // 2 for x in Counter(S).values()))