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

import sys
input = sys.stdin.readline
from collections import deque

H, W = map(int, input().split())
S = [list(input().split()[0]) for _ in range(H)]

def bfs(S, H, W, start, goal):
    INF = 100000000
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        if (x, y) == goal:
            break
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '#' and distance[next_y][next_x] == INF:
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return distance[goal[1]][goal[0]]

ans = 0
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                if (i, j) == (k, l) or S[i][j] == "#" or S[k][l] == "#":
                    continue
                start = (j, i)
                goal = (l, k)
                ans = max(ans, bfs(S, H, W, start, goal))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

H, W = map(int, input().split())
S = [list(input().split()[0]) for _ in range(H)]

def bfs(S, H, W, start):
    INF = -1
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '#' and distance[next_y][next_x] == -1:
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return max(map(max, distance))

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            ans = max(ans, bfs(S, H, W, (j, i)))
print(ans)
### BUGGY CODE ###

a, b, k = map(int, raw_input().split())
while k > 0:
  if a > 0:
    a -= 1
  elif b > 0:
    b -= 1
  k -= 1
print a, b

### FIXED CODE ###

a, b, k = map(int, raw_input().split())

na = max(0, a-k)
nb = max(0, b-(k-(a-na)))
print na, nb
### BUGGY CODE ###

p,q=map(int,input().split())
if q>p:
  p,q=q,p
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
g=gcd(p,q)
d=int(g**0.5)
res=set()
for i in range(2,g+1):
  if g%i!=0:
    continue
  else:
    res.add(i)
    while g%i==0:
      g=int(g/i)
print(len(res)+1)

### FIXED CODE ###

p,q=map(int,input().split())
if q>p:
  p,q=q,p
  
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
  
def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a
  
g=gcd(p,q)
res=prime_factorize(g)
print(len(res)+1)
### BUGGY CODE ###

a = input()
A = int(a)
P = 1
W = 1000000007
for i in range(A):
    P = P * (i+1)
P = P % W
print(P)

### FIXED CODE ###

import sys
a = sys.stdin.readline()
A = int(a)
P = 1
I = 1 
W = 10 ** 9 + 7
while I <= A:
    P *= I
    I += 1
    P %= W
print(P)
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [0] * (W+1)

for _ in range(N):
    w, v = map(int, input().split())
    for dp_w in reversed(range(W+1)):
        dp_v = dp[dp_w]
        if (dp_w == 0 or dp_v > 0) and dp_w + w <= W:
            dp[dp_w + w] = max(dp[dp_w + w], dp[dp_w] + v)

print(max(dp))

### FIXED CODE ###

N, W = map(int, input().split())
dp = [0] * (W+1)

for _ in range(N):
    w, v = map(int, input().split())
    for dp_w in reversed(range(W+1)):
        dp_v = dp[dp_w]
        if (dp_w == 0 or dp_v > 0) and dp_w + w <= W:
            dp[dp_w + w] = max(dp[dp_w + w], dp[dp_w] + v)

print(max(dp))
### BUGGY CODE ###

S=list(input())
T=list(input())
N=len(S)

i=-1
for t in T:
  if t in set(S[(i+1)%N:]):
    i+=S[(i+1)%N:].index(t)+1
  elif t in set(S[:(i+1)%N]):
    i+=len(S[(i+1)%N:])+S.index(t)+1
  else:
    print(-1)
    exit()
print(i+1)

### FIXED CODE ###

import bisect
S=list(input())
T=list(input())
sT=set(T)
N=len(S)
TI={}
for i in range(N):
  s=S[i]
  if s in sT:
    if s in TI:
      TI[s].append(i)
    else:
      TI[s]=[i]

i=-1
for t in T:
  if t not in TI:
    print(-1)
    exit()
  else:
    ni=TI[t][(bisect.bisect_right(TI[t],i%N))%len(TI[t])]
    if ni>i%N:
      i+=ni-i%N
    else:
      i+=N-i%N+ni
print(i+1)
### BUGGY CODE ###

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

for i, num in enumerate(a):
    if i % 2 != 0:
        b.append(num)
    else:
        b.insert(0, num)

if n % 2 == 0:
    b = b[::-1]

print(*b)

### FIXED CODE ###

import collections

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

for i, num in enumerate(a):
    if i % 2 != 0:
        b.append(num)
    else:
        b.appendleft(num)

if n % 2 == 0:
    b.reverse()

print(*b)
### BUGGY CODE ###

s = input()
# print(s)
t = s.replace("LR","L,R")
# print(t)
u = t.split(",")
# print(u)
ans = []
for i in u:
    L = len(i)
    # print(u[i])
    j = i.find("RL")
    # print(j)
    numR = j+1
    numL = L-(j+1)
    a = [0]*L
    a[j] = (numR+1)//2 + (numL)//2
    a[j+1] = (numR)//2 + (numL+1)//2
    ans = ans + a
print(" ".join(map(str, ans)))

### FIXED CODE ###

s = input()
l = len(s)
ans = [0]*l
count = 0
for i in range(l):
    if s[i]=="R" and s[i+1]=="R":
        count += 1
    elif s[i]=="R" and s[i+1]=="L":
        count += 1
        ans[i] += (count+1)//2
        ans[i+1] += count//2
        count = 0
for i in reversed(range(l)):
    # print(i)
    # print(s[i])
    if s[i]=="L" and s[i-1]=="L":
        count += 1
    elif s[i]=="L" and s[i-1]=="R":
        count += 1
        ans[i] += (count+1)//2
        ans[i-1] += count//2
        count = 0
print(" ".join(map(str, ans)))
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**9)

n, q = map(int, input().split())
neighbor = [[] for _ in range(n)]
point = [0]*n

for i in range(n-1):
    a, b = map(int, input().split())
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)

for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x


def dfs(now, past):
    for nv in neighbor[now]:
        if nv == past:
            continue
        point[nv] += point[now]
        dfs(nv, now)


dfs(0, -1)


print(*point)


### FIXED CODE ###

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

n, q = map(int, input().split())
neighbor = [[] for _ in range(n)]
point = [0]*n

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    neighbor[a].append(b)
    neighbor[b].append(a)

for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x


def dfs(now, past):
    for nv in neighbor[now]:
        if nv == past:
            continue
        point[nv] += point[now]
        dfs(nv, now)


dfs(0, -1)


print(*point)
### BUGGY CODE ###

import sys

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


def resolve():
    n, t = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    res = 0
    dp = [[0] * (t + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        a, b = AB[i - 1]
        for j in range(1, t + 1):
            if j - a >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a] + b)
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])
        now = dp[i - 1][t - 1] + b
        res = max(res, now)

    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

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


def resolve():
    n, t = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    res = 0
    dp = [[0] * (t + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        a, b = AB[i - 1]
        for j in range(1, t + 1):
            if j - a >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a] + b)
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])
        now = dp[i - 1][t - 1] + b
        res = max(res, now)

    print(res)


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

import sys

sys.setrecursionlimit(10**8)

N, W = map(int, input().split(" "))
WV = [list(map(int, input().split(" "))) for _ in range(N)]

l = [[None for _ in range(W+1)] for _ in range(N+1)]
def dp(i, limit):
    if i == -1:
        return 0
    if l[i][limit] != None:
        return l[i][limit]
    w, v = WV[i]
    if w <= limit:
        l[i][limit] = max(
            dp(i-1, limit),
            dp(i-1, limit-w) + v
        )
    else:
        l[i][limit] = dp(i-1, limit)
    return l[i][limit]

print(dp(N-1, W))

### FIXED CODE ###

N, W = map(int, input().split(" "))
WV = [list(map(int, input().split(" "))) for _ in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i, (w, v) in enumerate(WV):
    for j in range(W+1):
        if w <= j:
            dp[i+1][j] = max(
                dp[i][j-w] + v,
                dp[i][j]
            )
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])
### BUGGY CODE ###

a,b=map(int,input().split())
c=0
for i in range(40):
    j=2**i
    x,y=-(-a//(j*2))*j*2,b//(j*2)*j*2
    if x>=y:
        t=0
        for p in range(a,b+1):
            t+=p&j>0
    else:
        t=(y-x)//2
        for p in range(a,x):
            t+=p&j>0
        for p in range(y,b+1):
            t+=p&j>0
    c+=t%2*j
print(c)

### FIXED CODE ###

a,b=map(int,input().split())
c=0
for i in range(40):
    j=2**i
    x,y=-(-a//(j*2))*j*2,b//(j*2)*j*2
    """
    if x>=y:
        t=0
        for p in range(a,b+1):
            t+=p&j>0
    else:
    """
    t=(y-x)//2
    t+=min(j,x-a)
    t+=max(0,b-y-j+1)
    c+=t%2*j
print(c)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for r in range(N+1):
    for g in range(N+1):
        num_box, amari = divmod(N-R*r-G*g, B)
        if num_box >= 0 and amari == 0:
            ans += 1
print(ans)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for r in range(N+1):
    for g in range(N+1):
        num_box, amari = divmod(N-R*r-G*g, B)
        if num_box >= 0 and amari == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

K,S=map(int,input().split())
K+=1
ans=0
for i in range(K):
  if i>S:
    break
  for j in range(K):
    if i+j>S :
      break
    for k in range (K):
      if i+j+k>S:
        break
      if i+j+k==S:
        ans+=1
print(ans)

### FIXED CODE ###

K,S=map(int,input().split())
ans=0
#a=max(0,S-2*K)
for i in range(K+1):
  for j in range(K+1):
    if i+j+K>=S and i+j<=S :
      ans+=1

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

def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


n = int(input())
MOD = 998244353
fn, invs = prepare(n, MOD)
ans = pow(3, n, MOD)
impossible = 0
for i in range(n // 2):
    tmp = fn * invs[i] * invs[n - i] % MOD * pow(2, i, MOD)
    impossible = (impossible + 2 * tmp) % MOD
print((ans - impossible) % MOD)


### FIXED CODE ###

def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


n = int(input())
MOD = 998244353
fn, invs = prepare(n, MOD)
ans = pow(3, n, MOD)
impossible = 0
mul = 2
for i in range(n // 2):
    tmp = fn * invs[i] * invs[n - i] % MOD * mul
    impossible = (impossible + tmp) % MOD
    mul = mul * 2 % MOD
print((ans - impossible) % MOD)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)
n,q=map(int,input().split())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
px=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  px[p-1]+=x
ans=[0]*n
def dsf(index,u):
  ans[index]=ans[u]+px[index]
  for i in l[index]:
    if i==u:continue
    dsf(i,index)
dsf(0,-1)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
n,q=map(int,input().split())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
px=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  px[p-1]+=x
ans=[0]*n
def dsf(index,u):
  ans[index]=ans[u]+px[index]
  for i in l[index]:
    if i==u:continue
    dsf(i,index)
dsf(0,-1)
print(*ans)
### BUGGY CODE ###

"""
dp的な発想で解けるかな？
下の桁から見る。桁を一つずつ
"""
from collections import defaultdict
S = input()
N = len(S)
S = S[::-1]

ans = 0
memo = defaultdict(int)
num = 0
memo[0] = 1
for i in range(N):
    num = (num+pow(10,i)*int(S[i])%2019)%2019
    ans += memo[num]
    memo[num] += 1

print(ans)

### FIXED CODE ###

"""
dp的な発想で解けるかな？
下の桁から見る。桁を一つずつ
"""
from collections import defaultdict
S = input()
N = len(S)
S = S[::-1]

ans = 0
memo = defaultdict(int)
num = 0
memo[0] = 1
for i in range(N):
    num = (num+(pow(10,i,2019)*int(S[i]))%2019)%2019
    ans += memo[num]
    memo[num] += 1

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

from collections import deque
n, m = map(int, input().split(' '))
c = [[] for i in range(n)]
r = [0] * n
q = deque()
for i in range(m):
    a, b = map(int, input().split(' '))
    c[a - 1].append(b - 1)
    c[b - 1].append(a - 1)
q.append([0] + c[0])
while(len(q) > 0):
    g = q.popleft()
    ix = g.pop(0)
    for i in g:
        r[i] = ix + 1 if r[i] == 0 else r[i]
        if len(c[i]) > 0:
            t = [i] + [j for j in c[i] if r[j] == 0]
            if len(t) > 1:
                q.append(t)
jg = 'Yes' if r.pop(0) > 0 else 'No'
print(jg)
for i in r:
    print(i)

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split(' '))
c = [[] for i in range(n)]
r = [0] * n
q = deque()
for i in range(m):
    a, b = map(int, input().split(' '))
    c[a - 1].append(b - 1)
    c[b - 1].append(a - 1)
q.append(0)
while len(q) > 0:
    ix = q.popleft()
    for i in c[ix]:
        if r[i] == 0:
            r[i] = ix + 1
            q.append(i)

jg = 'Yes' if r.pop(0) > 0 else 'No'
print(jg)
for i in r:
    print(i)
### BUGGY CODE ###

import queue
n = int(input())

tree = {i: [] for i in range(n)}

for _ in range(n-1):
  t = input().split()
  u, v = int(t[0]), int(t[1])
  tree[u-1].append(v-1)
  tree[v-1].append(u-1)

a = 0
q = queue.Queue()
q.put(a)
v = [0 for _ in range(n)]
v[a] = 1

while (not q.empty()):
    a = q.get()
    for b in tree[a]:
        if (v[b] == 0):
            q.put(b)
            v[b] = 1

s = a
q = queue.Queue()
q.put([a, 1])
v = [0 for _ in range(n)]
v[a] = 1

while (not q.empty()):
    a = q.get()
    for b in tree[a[0]]:
        if (v[b] == 0):
            q.put([b, a[1] + 1])
            v[b] = 1

l = a[1]
if l%3 == 2:
    print("Second")
else:
    print("First")



### FIXED CODE ###

import queue
n = int(input())

tree = {i: [] for i in range(n)}

for _ in range(n-1):
  t = input().split()
  u, v = int(t[0]), int(t[1])
  tree[u-1].append(v-1)
  tree[v-1].append(u-1)

a = 0
q = queue.Queue()
q.put(a)
v = [0 for _ in range(n)]
v[a] = 1

while (not q.empty()):
    a = q.get()
    for b in tree[a]:
        if (v[b] == 0 and len(tree[b]) > 1):
            q.put(b)
            v[b] = 1

s = a
q = queue.Queue()
q.put([a, 1])
v = [0 for _ in range(n)]
v[a] = 1

while (not q.empty()):
    a = q.get()
    for b in tree[a[0]]:
        if (v[b] == 0 and len(tree[b]) > 1):
            q.put([b, a[1] + 1])
            v[b] = 1

if n <= 3:
    l = n
else:
	l = a[1] + 2

if l%3 == 2:
    print("Second")
else:
    print("First")
### BUGGY CODE ###

A, B, C, D = map(int, input().split())

cnt = 0
for i in range(A, B + 1):
  if i % C != 0 and i % D != 0:
    cnt += 1
    
print (cnt)

### FIXED CODE ###

A, B, C, D = map(int, input().split())

def gcd(a, b):
  if b > a:
    a, b = b, a
  a,b = b, a % b
  if b == 0:
    return a
  else:
    return gcd(a, b)
G = C * D // gcd(C, D)

print (B -B // C - B // D + B // G -(A-1)+ (A-1) // C + (A-1) // D - (A-1) // G)
### BUGGY CODE ###

import math

k = int(input().strip())
gcdsum = 0

for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            gcdsum += math.gcd(math.gcd(a, b), c)
print(gcdsum)

### FIXED CODE ###

import math
import itertools

k = int(input().strip())
gcdsum = 0

for a, b, c in itertools.combinations_with_replacement(range(1, k + 1), 3):
    if a == b and b == c:
        gcdsum += math.gcd(math.gcd(a, b), c) * 1
    elif a != b and b == c:
        gcdsum += math.gcd(math.gcd(a, b), c) * 3
    elif a == b and b != c:
        gcdsum += math.gcd(math.gcd(a, b), c) * 3
    elif a != b and b != c:
        gcdsum += math.gcd(math.gcd(a, b), c) * 6
print(gcdsum)
### BUGGY CODE ###

H,W = map(int, input().split())
A = []
for _ in range(H):
    A += [ [ 1 if x == "#" else 0 for x in input()] ]

import numpy as np


A = np.array(A)
WK = np.zeros(A.shape, np.int32)
i = 0
S = H * W
while True:
    if np.min(A) == 1:
        break
    WK -= WK
    WK += A
    A[:-1] |= WK[1:]
    A[1:] |= WK[:-1]
    A[:,:-1] |= WK[:,1:]
    A[:,1:] |= WK[:,:-1]
    i += 1

print(i)


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)
### BUGGY CODE ###

H, W, D = map(int,input().split())
dist = [[float("inf") for i in range(H*W+1)] for j in range(H*W+1)]
for i in range(H*W+1):
  dist[i][i] = 0
#dist[i][j]は隣接行列
pos = [[0,0] for i in range(H*W+1)]
for i in range(H):
  A = list(map(int,input().split()))
  for j in range(W):
    pos[A[j]] = [i+1, j+1]
for i in range(H*W+1-D):
  dist[i][i+D] = abs(pos[i][0]-pos[i+D][0])+abs(pos[i][1]-pos[i+D][1])
distances = [[] for i in range(D)]#あまりがiの距離
for i in range(1,H*W+1-D):
  d = dist[i][i+D]
  distances[i%D]+=[d]
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  q = L%D
  l, r = (L-1)//D, (R-1)//D
  print(sum(distances[q][l:r]))

### FIXED CODE ###

H, W, D = map(int,input().split())
dist = [0]*(H*W+1)#dist[i]はiからi+Dまでの距離
pos = [[0,0] for i in range(H*W+1)]
for i in range(H):
  A = list(map(int,input().split()))
  for j in range(W):
    pos[A[j]] = [i+1, j+1]
for i in range(H*W+1-D):
  dist[i] = abs(pos[i][0]-pos[i+D][0])+abs(pos[i][1]-pos[i+D][1])
distances = [[] for i in range(D)]#あまりがiの距離
for i in range(1,H*W+1-D):
  d = dist[i]
  distances[i%D]+=[d]
distances2 = [[0] for i in range(D)]#累積和に直す
for i in range(D):
  for j in range(len(distances[i])):
    distances2[i]+=[distances2[i][-1]+distances[i][j]]
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  q = L%D
  l, r = (L-1)//D, (R-1)//D
  print(distances2[q][r]-distances2[q][l])
### BUGGY CODE ###

from collections import Counter
import math
n,m = map(int, input().split())
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def prime_decomposition(n, table):
    i = 2
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
table = []
prime_decomposition(m, table)
c = Counter(table).values()
cc = Counter(c)
ans = 1
N = n-1
for i,j in cc.items():
  ans *= ((combinations_count(N+i,i))**j)%(10**9+7)
print(ans%(10**9+7))


### FIXED CODE ###

from collections import Counter
import math
n,m = map(int, input().split())
def combinations_count(n, r):
    l = 1
    for num in range(1,r+1):
      l *= (n+num)
      l = l // num
    return l
def prime_decomposition(n, table):
    i = 2
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
table = []
prime_decomposition(m, table)
c = Counter(table).values()
cc = Counter(c)
ans = 1
N = n-1
for i,j in cc.items():
  ans *= ((combinations_count(N,i))**j)%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

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

def main():
    a_added = [a[i] + i for i in range(n)]
    a_substracted = [j - a[j] for j in range(n)]
    c = 0
    for i in range(n):
        c += a_substracted.count(a_added[i])
            
    print(c)
main()

### FIXED CODE ###

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

L = [i+A[i] for i in range(N)]
R = [i-A[i] for i in range(N)]

p = {}
m = {}
for i in range(N):
    if L[i] not in p:
        p[L[i]] = 1
    else:
        p[L[i]] += 1
for i in range(N):
    if R[i] not in m:
        m[R[i]] = 1
    else:
        m[R[i]] += 1

lower = max(min(p), min(m))
upper = min(max(p), max(m))
ans = 0
for x in range(lower, upper + 1):
    if x in p and x in m:
        ans += p[x] * m[x]

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

from sys import stdin, stdout

input = stdin.readline()[:-1].split(' ')

takahashi = int(input[0])
aoki = int(input[1])
k = int(input[2])

for n in range(k):
    if takahashi > 0:
        takahashi -= 1
    elif aoki > 0:
        aoki -= 1

print('{} {}'.format(takahashi, aoki))


### FIXED CODE ###

from sys import stdin, stdout

input = stdin.readline()[:-1].split(' ')

takahashi = int(input[0])
aoki = int(input[1])
k = int(input[2])

if k > 0:
    if takahashi > k:
        prev_k = k
        takahashi = takahashi - prev_k
        k = prev_k - takahashi
    else:
        k = k - takahashi
        takahashi = 0

if k > 0:
    if aoki > k:
        aoki = aoki - k
    else:
        aoki = 0

print('{} {}'.format(takahashi, aoki))
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline().rstrip())
def S(): return sys.stdin.readline().rstrip()

N = I()
s = [sorted(S()) for i in range(N)]

ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        if s[i] == s[j]:
            ans += 1

print(ans)


### FIXED CODE ###

import sys
def I(): return int(sys.stdin.readline().rstrip())
def S(): return sys.stdin.readline().rstrip()

N = I()
s = [''.join(sorted(S())) for i in range(N)]

from collections import Counter

c = Counter(s)
ans = 0
for i in c.keys():
    ans += c[i]*(c[i]-1)//2

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

S = list(input())
Q = int(input())
reverse = False
for i in range(Q):
  q = input()
  if q == "1":
    reverse = not reverse
  else:
    q,f,c = q.split()
    if (f == "1" and not reverse) or (f == "2" and reverse):
      S = [c]+S
    else:
      S = S+[c]
if not reverse:
  print("".join(S))
else:
  print("".join(reversed(S)))

### FIXED CODE ###

import collections
S = collections.deque(input())
Q = int(input())
reverse = False
for i in range(Q):
  q = input()
  if q == "1":
    reverse = not reverse
  else:
    q,f,c = q.split()
    if (f == "1" and not reverse) or (f == "2" and reverse):
      S.appendleft(c)
    else:
      S.append(c)
if not reverse:
  print("".join(S))
else:
  print("".join(reversed(S)))