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

from collections import deque

H, W = map(int, input().split())
s = ["X" * (W+2)] + ["X" + input() + "X" for _ in range(H)] + ["X" * (W+2)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

ans = 0
def bfs(start):
	global ans
	que = deque([start])
	visited = [[False for _ in [0]*(W+2)] for _ in [0]*(H+2)]
	visited[start[0]][start[1]] = True
	#cur = s[start[0]][start[1]]
	while que:
		label = que.pop()
		h, w = label[0], label[1]
		if s[start[0]][start[1]] != s[h][w] and W*start[0]+start[1] < W*h+w:
			ans += 1
		for dh, dw in zip(DH, DW):
			if s[h][w] == ".":
				if s[h+dh][w+dw] == "#" and visited[h+dh][w+dw] == False:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = True
			elif s[h][w] == "#":
				if s[h+dh][w+dw] == "." and visited[h+dh][w+dw] == False:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = True


	del que, visited
	return

for i in range(1, H+1):
	for j in range(1, W+1):
		bfs([i, j])

print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
s = ["X" * (W+2)] + ["X" + input() + "X" for _ in range(H)] + ["X" * (W+2)]
visited = [[-1 for _ in range(W+2)] for _ in range(H+2)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

ans = 0
def bfs(start, num):
	global ans
	dot, sharp = 0, 0
	que = deque([start])
	#visited = [[False for _ in [0]*(W+2)] for _ in [0]*(H+2)]
	visited[start[0]][start[1]] = num
	#cur = s[start[0]][start[1]]
	while que:
		label = que.pop()
		h, w = label[0], label[1]
		if s[h][w] == ".":
			dot += 1
		elif s[h][w] == "#":
			sharp += 1
		#if s[start[0]][start[1]] != s[h][w] and W*start[0]+start[1] < W*h+w:
			#ans += 1
		for dh, dw in zip(DH, DW):
			if s[h][w] == ".":
				if s[h+dh][w+dw] == "#" and visited[h+dh][w+dw] == -1:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = num
			elif s[h][w] == "#":
				if s[h+dh][w+dw] == "." and visited[h+dh][w+dw] == -1:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = num
	#del que, visited
	return dot*sharp

k = 0
for i in range(1, H+1):
	for j in range(1, W+1):
		if visited[i][j] == -1:
			ans += bfs([i, j], k)

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

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

ld={}
for i in range(n):
    ld.setdefault(i,l[i])

ans=0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if ld[i]+ld[j]>ld[k] and ld[j]+ld[k]>ld[i] and ld[k]+ld[i]>ld[j]:
                ans+=1
            #print(l[i],l[j],l[k])

print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
ls = sorted(l)

ld={}
for i in range(n):
    ld.setdefault(i,ls[i])
#print(ld)

ans=0
for i in range(n-2):
    for j in range(i+1, n-1):
        k = bisect.bisect_left(ls, ld[i]+ld[j])
        #print(k)
        ans += k-j-1

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

import math
 
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
t.sort(reverse=True)
for i in range(s[1]):
  t[0]=math.floor(t[0]/2)
  if s[0]>=2:
    if t[0]<t[1]:
      t.sort(reverse=True)
  else:
    continue
a=sum(t)
print(a)

### FIXED CODE ###

import math
 
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=0
c=0
d=s[1]
t.sort(reverse=True)
if s[0]==1:
  for i in range(s[1]):
    t[0]=math.floor(t[0]/2)
else:
  c=t[0]/2
  for j in range(s[1]):
    for l in range(s[0]):
      if d>0:
        if c<t[l]:
          t[l]=math.floor(t[l]/2)
          d=d-1
        else:
            t.sort(reverse=True)
            c=t[0]/2
            break
      else:
        break
e=sum(t)
print(e)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

rm = n // r
gm = n // g
count = 0
for i in range(rm + 1):
    for j in range(gm + 1):
        if ((n - r * i - g * j) % b == 0 and (n - r * i - g * j) // b >= 0):
            count += 1

print(count)


### FIXED CODE ###

r, g, b, n = map(int, input().split())

rm = n // r
gm = n // g
count = 0
for i in range(rm + 1):
    for j in range(gm + 1):
        if ((n - r * i - g * j) % b == 0 and (n - r * i - g * j) // b >= 0):
            count += 1

print(count)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

b = []
count = 0
for i in a:
  if count % 2 == 0:
    b.append(i)
  else:
    b.insert(0, i)
  count += 1

if n % 2 == 0:
  print(' '.join([str(i) for i in b]))
else: 
  b.reverse()
  print(' '.join([str(i) for i in b]))


  

### FIXED CODE ###

n=int(input())
a=list(input().split())
b=[]
if len(a)%2==0:
  for i in range(n-1,0,-2):
    b.append(a[i])
  for i in range(0,n-1,2):
    b.append(a[i])
else:
  for i in range(n-1,-1,-2):
    b.append(a[i])
  for i in range(1,n-1,2):
    b.append(a[i])
print(' '.join(b))
### BUGGY CODE ###

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

mod = 10**9 + 7

out = 0
for i in range(n - 1):
    for j in range(n - i - 1):
        k = i + j + 1
        # print(A[i], A[k])
        out += ((A[i] % mod) * (A[k] % mod))
        out %= mod
print(out)

### FIXED CODE ###

mod = 10**9 + 7
n = int(input())
A = list(map(lambda x: int(x) % mod, input().split()))

# out = 0
# for i in range(n - 1):
#     for j in range(n - i - 1):
#         k = i + j + 1
#         # print(A[i], A[k])
#         out += (A[i] * A[k])
#         out %= mod
B = A[1:n]
B_s = 0
for i in range(n - 1):
    B_s += B[i] % mod

out = 0
for i in range(n - 1):
    out += A[i] * B_s
    out %= mod
    B_s -= A[i + 1]
    B_s %= mod
    if B_s < 0:
        B_s += mod

print(out)
### BUGGY CODE ###

import math
sum=0
num=int(input())
for a in range(1,num+1):
  for b in range(1,num+1):
    for c in range(1,num+1):
      d=math.gcd(a,b)
      e=math.gcd(c,d)
      sum=sum+e
print(sum)

### FIXED CODE ###

import math
sum=0
num=int(input())
for a in range(1,num+1):
  for b in range(1,num+1):
    for c in range(1,num+1):
      d=math.gcd(a,b)
      e=math.gcd(c,d)
      sum=sum+e
print(sum)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
from queue import Queue

N, Q = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(N-1):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

score = [0 for _ in range(N+1)]
for _ in range(Q):
    p, x = map(int, input().split())
    score[p] += x

def dfs(now, prev):
    for target in adj[now]:
        if target == prev:
            continue
        score[target] += score[now]
        dfs(target, now)

dfs(1, 0)

print(" ".join(map(str, score[1:])))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
from queue import Queue

def input():
    return sys.stdin.readline()

N, Q = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(N-1):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

score = [0 for _ in range(N+1)]
for _ in range(Q):
    p, x = map(int, input().split())
    score[p] += x

def dfs(now, prev):
    for target in adj[now]:
        if target == prev:
            continue
        score[target] += score[now]
        dfs(target, now)

dfs(1, 0)

print(" ".join(map(str, score[1:])))
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline
    INF = 10**15
    N, M = map(int, input().split())
    heap = []
    for _ in range(M):
        l, r, c = map(int, input().split())
        heappush(heap, (l-1, r-1, c))
    
    dp = [INF]*N
    dp[0] = 0
    while heap:
        l, r, c = heappop(heap)
        if dp[l] == INF:
            return -1
        
        for i in range(l+1, r+1):
            dp[i] = min(dp[i], dp[l] + c)
        
    if dp[N-1] == INF:
        return -1
    
    return dp[N-1]

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import sys
from heapq import heappop, heappush, heapify

def dijkstra(s, t, links):
    """Dijkstra algorism
    s: int, start node.
    t: int, target node.
    links: iterable, link infomation.
           links[i] contains edges from node i: (cost, target_node).

    return int, minimal cost from s node to t node.
    """
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while len(heap) > 0:
        cost, node = heappop(heap)
        if node == t:
            return cost

        if node in visited:
            continue

        visited.add(node)
        for cost2, node2 in links[node]:
            if node2 in visited:
                continue

            heappush(heap, (cost + cost2, node2))

    return -1

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    links = [[] for _ in range(N)]
    for i in range(1, N):
        links[i].append((0, i-1))

    for _ in range(M):
        l, r, c = map(int, input().split())
        links[l-1].append((c, r-1))
    
    return dijkstra(0, N-1, links)
    

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

import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

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

def less(x):
    res = 0
    for i in range(N):
        e = A[i]
        if e < 0:
            res += i - bisect_right(A, x // e, 0, i)
        elif e > 0:
            res += bisect_left(A, - (- x // e), 0, i)
        elif x > 0:
            res += i
    return res

l = - (10 ** 18 + 1)
r = - l
while l + 1 < r:
    m = (l + r) // 2
    if less(m) < K:
        l = m
    else:
        r = m
print(l)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

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

neg = bisect_left(A, 0)
pos = bisect_right(A, 0)

def less(x):
    res = 0
    b = 0
    for i in range(0, neg):
        while b != N and A[i] * A[b] >= x:
            b += 1
        while b != 0 and A[i] * A[b - 1] < x:
            b -= 1
        res += max(i - b, 0)
    for i in range(neg, pos):
        if x > 0:
            res += i
    for i in range(pos, N):
        while b != N and A[i] * A[b] < x:
            b += 1
        while b != 0 and A[i] * A[b - 1] >= x:
            b -= 1
        res += min(b, i)
    return res

l = - (10 ** 18 + 1)
r = - l
while l + 1 < r:
    m = (l + r) // 2
    if less(m) < K:
        l = m
    else:
        r = m
print(l)
### BUGGY CODE ###

import math

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

if abs(N - M) > 1:
    print(0)
elif abs(N - M) == 1:
    print(math.factorial(N) * math.factorial(M))
else:
    print((math.factorial(N) ** 2 * 2) % (10 ** 9 + 7))


### FIXED CODE ###

import math

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

if abs(N - M) > 1:
    print(0)
elif abs(N - M) == 1:
    print((math.factorial(N) * math.factorial(M)) % (10 ** 9 + 7))
else:
    print((math.factorial(N) ** 2 * 2) % (10 ** 9 + 7))
### BUGGY CODE ###

def D_joisino_travel(N, M, R, r, A):
    """
    N:国の中の町の数
    M:町を結ぶ道の総数
    R:訪れる町の数
    r:訪れる町の番号
    A:町の結び方とその間の距離
    """
    from itertools import permutations
    # 0行、0列は使わない(番号と配列の要素番号を一致させるため)
    dist = [[float('inf') for i in range(N + 1)] for j in range(N + 1)]
    for i in range(1, N + 1):
        dist[i][i] = 0
    for m, n, c in A:
        dist[m][n] = c
        dist[n][m] = c

    # ワーシャルフロイド法(町A→Bの最短距離を求められる)
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    permutation_route = permutations(r)
    min_dist = float('inf')
    for i in permutation_route:
        cost = 0
        for j in range(len(i) - 1): # i(行く町の順列)の先頭から2つ要素を拾う
            cost += dist[i[j]][i[j + 1]] # コストはワーシャルフロイド法で求めてある
        min_dist = min(min_dist, cost)
    return min_dist
  
N,M,R = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for i in range(M)]
print(D_joisino_travel(N, M, R, r, A))

### FIXED CODE ###

def D_joisino_travel(N, M, R, r, A):
    """
    N:国の中の町の数
    M:町を結ぶ道の総数
    R:訪れる町の数
    r:訪れる町の番号
    A:町の結び方とその間の距離
    """
    from itertools import permutations
    INF = float('inf')
    # 道の番号-1が要素の番号
    r = [x - 1 for x in r]
    dist = [[INF]*N for j in range(N)]
    for i in range(N):
        dist[i][i] = 0
    for m, n, c in A:
        m-=1
        n-=1
        dist[m][n] = c
        dist[n][m] = c

    # ワーシャルフロイド法(町A→Bの最短距離を求められる)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    permutation_route = permutations(r)
    min_dist = INF
    for i in permutation_route:
        cost = 0
        for j in range(R - 1):  # i(行く町の順列)の先頭から2つ要素を拾う
            cost += dist[i[j]][i[j + 1]]  # コストはワーシャルフロイド法で求めてある
        min_dist = min(min_dist, cost)
    return min_dist
  
N,M,R = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for i in range(M)]
print(D_joisino_travel(N, M, R, r, A))
### BUGGY CODE ###

import sys
from collections import deque

input = sys.stdin.readline

h, w = map(int, input().split())
# 蛮兵
painted = [['#'] * (w + 2)]
painted += [['#'] + list(input().rstrip()) + ['#'] for _ in range(h)]
painted.append(['#'] * (w + 2))
que = deque()

for y in range(1, h + 1):
    for x in range(1, w + 1):
        if painted[y][x] == '#':
            painted[y][x] = 0
            que.append((y, x))
cnt = 0
while que:
    y, x = que.popleft()
    if painted[y - 1][x] == '.':
        painted[y - 1][x] = painted[y][x] + 1
        que.append((y - 1, x))
    if painted[y + 1][x] == '.':
        painted[y + 1][x] = painted[y][x] + 1
        que.append((y + 1, x))
    if painted[y][x + 1] == '.':
        painted[y][x + 1] = painted[y][x] + 1
        que.append((y, x + 1))
    if painted[y][x - 1] == '.':
        painted[y][x - 1] = painted[y][x] + 1
        que.append((y, x - 1))
print(painted[y][x])

### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    h, w = map(int, input().split())
    # 蛮兵
    painted = [['#'] * (w + 2)]
    painted += [['#'] + list(input().rstrip()) + ['#'] for _ in range(h)]
    painted.append(['#'] * (w + 2))
    que = []

    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if painted[y][x] == '#':
                painted[y][x] = 0
                que.append((y, x))
    while que:
        qq = []
        for y, x in que:
            if painted[y - 1][x] == '.':
                painted[y - 1][x] = painted[y][x] + 1
                qq.append((y - 1, x))
            if painted[y + 1][x] == '.':
                painted[y + 1][x] = painted[y][x] + 1
                qq.append((y + 1, x))
            if painted[y][x + 1] == '.':
                painted[y][x + 1] = painted[y][x] + 1
                qq.append((y, x + 1))
            if painted[y][x - 1] == '.':
                painted[y][x - 1] = painted[y][x] + 1
                qq.append((y, x - 1))
        que = qq

    print(painted[y][x])


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

N = int(input())
S = input()

def main(N,S):
    count=0
    for i in range(1,N-2 +1):
        for j in range(i+1, N-1 +1):
            for k in range(j+1, N +1):
                if j-i != k-j and S[i-1]!=S[j-1]!=S[k-1]!=S[i-1]:
                    count += 1
    print(count)

if __name__=='__main__':
    main(N,S)

### FIXED CODE ###


N=int(input())
S=input()

#(RGB)になる組み合わせをカウント
count= S.count("R")*S.count("G")*S.count("B")
count0=0

#条件を満たさないものを引いていく
for i in range(1,N-2 +1):
    for j in range(i+1,(N+i)//2 +1):
        k=2*j-i
        if S[k-1]!=S[i-1] and S[k-1]!=S[j-1] and S[i-1]!=S[j-1]:
            count0 += 1
print(count-count0)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(n):
    ans.append(a.index(i+1)+1)
print(*ans)



### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
keys = []
for i in range(n):
    keys.append(i+1)
dic = {key: val for key,val in zip(keys,a)}
dic_sorted = sorted(dic.items(),key = lambda x:x[1])
for i in range(n):
    print(dic_sorted[i][0],end=" ")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in a:
    ans *= i

if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))
ans = 1
flag = True
if 0 in a:
    print(0)
    sys.exit()

for i in a:
    ans *= i
    if ans > 1000000000000000000:
        flag = False
        break

if flag == False:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import collections

N = int(input())

S_list = []

for i in range(N):
    s = input()
    S_list.append(s)

c = collections.Counter(S_list)
c_max = c.most_common()
max_num = c.most_common()[0][1]
ans_list = []
ans_list.append(c.most_common()[0][0])

for i in range(1, len(c_max)):
    if c.most_common()[i][1] != max_num:
        break
    else:
        ans_list.append(c.most_common()[i][0])

print(*sorted(ans_list), sep='\n')

### FIXED CODE ###

import collections

N = int(input())

S_list = []

for i in range(N):
    s = input()
    S_list.append(s)

c = collections.Counter(S_list)
c_max = c.most_common()
max_num = c.most_common()[0][1]
ans_list = []
ans_list.append(c.most_common()[0][0])

for i in range(1, len(c_max)):
    if c_max[i][1] != max_num:
        break
    else:
        ans_list.append(c_max[i][0])

print(*sorted(ans_list), sep='\n')
### BUGGY CODE ###

def main():
    h,*s=open(0)
    s=[tuple(t[:-1])for t in s]
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*h for _ in range(w))
    d=tuple([0]*h for _ in range(w))
    for t,x,y in zip(s,a,b):
        x[0]=int(t[0]=='.')
        for i,u in enumerate(t[1:]):
            x[i+1]=x[i]+1if u=='.'else 0
        y[-1]=int(t[-1]=='.')
        for i,u in enumerate(t[-2::-1],1):
            y[~i]=y[-i]+1if u=='.'else 0
    for t,x,y in zip(zip(*s),c,d):
        x[0]=int(t[0]=='.')
        for i,u in enumerate(t[1:]):
            x[i+1]=x[i]+1if u=='.'else 0
        y[-1]=int(t[-1]=='.')
        for i,u in enumerate(t[-2::-1],1):
            y[~i]=y[-i]+1if u=='.'else 0
    print(max(sum(u)-3for t in zip(a,b,tuple(zip(*c)),tuple(zip(*d)))for u in zip(*t)))
main()

### FIXED CODE ###

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in range(h)for j in range(w)))
main()
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = sorted(LIST())

m = int(sqrt(a[-1]))
primes = set(range(2, m+1))
for i in range(2, int(m**0.5+1)):
    primes.difference_update(range(i*2, m+1, i))
primes=list(primes)

for i in range(n):
    for x in primes:
        y = x * x
        if y > a[i]:
            break
        else:
            while a[i] % y == 0:
                a[i] //= x

k = 1
flag = 1
for i in range(1, n):
    k *= a[i-1]
    if gcd(k, a[i]) > 1:
        flag = 0
        break

if flag == 1:
    print("pairwise coprime")
    exit()
else:
    g = a[0]
    for i in range(1, n):
        g = gcd(g, a[i])
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = LIST()
m = max(a)

primes = [0]*(m+1)
primes[1] = 1
for i in range(2, m+1):
    if primes[i] == 0:
        for j in range(1, m//i+1):
            primes[i*j] = i

count = [0]*(m+1)
for x in a:
    y = x
    while primes[y] != y:
        count[primes[y]] += 1
        p = primes[y]
        while y % p == 0:
            y //= p
    if primes[y] >= 2:
        count[primes[y]] += 1

if max(count) <= 1:
    print("pairwise coprime")
else:
    g = 0
    for x in a:
        g = gcd(g, x)
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")
### BUGGY CODE ###

import re
import copy

def getDevidedString(S):
    s = copy.deepcopy(S)
    regExDream = "^(.*)dream$"
    if re.match(regExDream, s):
        return re.sub(regExDream, "\\1", s)
    regExDreamer = "^(.*)dreamer$"
    if re.match(regExDreamer, s):
        return re.sub(regExDreamer, "\\1", s)
    regExErase = "^(.*)erase$"
    if re.match(regExErase, s):
        return re.sub(regExErase, "\\1", s)
    regExEraser = "^(.*)eraser$"
    if re.match(regExEraser, s):
        return re.sub(regExEraser, "\\1", s)
    return s

S = input()

while len(S) != 0:
    tmp = getDevidedString(S)
    if len(S) != len(tmp):
        S = tmp
    else:
        break

if len(S)== 0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

d = ["dream", "dreamer", "erase", "eraser"]

def getDevidedString(s):
    i = 0
    while i < 4:
        position = len(d[i]) * -1
        str = s[position:]
        if str == d[i]:
           return s[0:position]
        i += 1
    return s

S = input()

while len(S) != 0:
    tmp = getDevidedString(S)
    if len(S) != len(tmp):
        S = tmp
    else:
        break

if len(S)== 0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

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

map = {}
i = 2
while m != 1:
    if m % i == 0 :
        m = m / i
        if i in map:
            map[i] += 1
        else:
            map[i] = 1
    else:
        i += 1
sum = 1
for i in map:
    tmpn = n + map[i] - 1
    c = 1
    d = 1
    e = 1
    for j in range(map[i]):
        c = c * (tmpn - j)
        d = d * (map[i] - j)
    e = e * c // d
    
    sum = sum * e
print(sum % 1000000007)

### FIXED CODE ###

import math
(n, m)  =map(int, input().split())
sqm = math.sqrt(m)
map = {}
i = 2
y = m
while m != 1 and sqm >= i:
    if m % i == 0 :
        m = m / i
        if i in map:
            map[i] += 1
        else:
            map[i] = 1
    else:
        i += 1
if m > 1:
    map[m] = 1

sum = 1
for i in map:
    tmpn = n + map[i] - 1
    c = 1
    d = 1
    e = 1
    for j in range(map[i]):
        c = c * (tmpn - j)
        d = d * (map[i] - j)
    e = e * c // d
    
    sum = sum * e % 1000000007
print(sum )