Harryxun/stf_run huggingface dataset:
import sys
from heapq import *

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

ans=-1
hp=[(0,si,sj)]
dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    if k>dist[i][j]:
        continue
    dist[ni][nj]=nk
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='#':
                continue
            if abs(di)+abs(dj)==1:
                nk=k
            else:
                nk=k+1
            heappush(hp,(nk,ni,nj))

print(ans)


### FIXED CODE ###

import sys
from heapq import *

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

ans=-1
hp=[(0,si,sj)]
dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    if k>dist[i][j]:
        continue
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='#':
                continue
            if abs(di)+abs(dj)==1:
                nk=k
            else:
                nk=k+1
            if nk>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            heappush(hp,(nk,ni,nj))

print(ans)
N = int(input())
if (N % 1000) != 0:
    ans = 1000 - N % 1000
elif:
    ans = 0
print(ans)

### FIXED CODE ###

N = int(input())
if (N % 1000) != 0:
    ans = 1000 - N % 1000
else:
    ans = 0
print(ans)
def dfs(v, d):
    for u in g[v]:
        if d[u] != init:
            continue
        d[u] = d[v] + 1
        dfs(u, d)


def main():
    import sys
    input = sys.stdin.readline

    global g, init

    n = int(input())

    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    init = n

    dist_1 = [init] * n
    dist_1[0] = 0
    dfs(0, dist_1)

    dist_n = [init] * n
    dist_n[n - 1] = 0
    dfs(n - 1, dist_n)

    fennec = sum(dist_1[v] <= dist_n[v] for v in range(n))
    snuke = n - fennec

    if fennec > snuke:
        print('Fennec')
    else:
        print('Snuke')


if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/abc067/submissions/2975640

from collections import deque

INF = 10 ** 5 + 10

N = int(input())
f = [INF for _ in range(N)]
# f[v]:=頂点0からの最短距離
s = [INF for _ in range(N)]
# s[v]:=頂点N-1からの最短距離

e = [[] for _ in range(N)]
# 道, 隣接リスト, 0-indexed

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    # 0-indexed
    e[a].append(b)
    e[b].append(a)

q = deque()
q.append((0, 0))

while q:
    v, d = q.popleft()
    f[v] = d
    for nv in e[v]:
        if f[nv] <= d + 1: continue
        q.append((nv, d + 1))

q = deque()
q.append((N - 1, 0))

while q:
    v, d = q.popleft()
    s[v] = d
    for nv in e[v]:
        if s[nv] <= d + 1: continue
        q.append((nv, d + 1))

Fennec_count = 0
for v in range(N):
    if f[v] <= s[v]:
        # 頂点0から近い場合
        # 等距離なら先に塗れる黒になる
        Fennec_count += 1
        # 黒

print('Fennec' if Fennec_count > N - Fennec_count else 'Snuke')
N = list(input())
if N%10 != 0:
    res = 0
    for i in range(len(N)):
        res += int(N[i])
else:
    res = 10
print(res)

### FIXED CODE ###

N = list(input())
if int(''.join(N))%10 != 0:
    res = 0
    for i in range(len(N)):
        res += int(N[i])
else:
    res = 10
print(res)
N,Y = map(int, input().split())


a = -1
b = -1
c = -1

flag = 0

for i in range(N + 1):
    if flag == 1:
        break
    if  Y - 10000 * i  == 0:
        a = i
        b = 0
        c = 0
    if  Y - 10000 * i - 5000 * N  >= 0:        
        for j in range(N + 1 - i):
            if flag == 1:
                break
                if  Y - 10000 * i - 5000 * j - 1000 * N > =0:
                    for k in range(N + 1 -  i - j):
                        if Y - 10000 * i - 5000 * j - 1000 * k == 0:
                            a = i
                            b = j
                            c = k
                            flag = 1
                            break


print(str(a) +' '+ str(b) +' ' + str(c))


### FIXED CODE ###

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


a = -1
b = -1
c = -1

flag = 0

for i in range(N + 1):
    if flag == 1:
        break
    if  Y - 10000 * i  ==0 and i==N:
        a = i
        b = 0
        c = 0
        flag = 1

    if Y - 10000 * i > 0:
        for j  in range(N+1- i):
                k = N - i -j
                if Y - 10000 * i - 5000 * j - 1000 * k == 0:
                    a = i
                    b = j
                    c   = k
                    flag = 1
                    break


print(str(a) +' '+ str(b) +' '+ str(c))
N = int(input())
a = N[-1]
if a in [0,1,6,8]:
  print("pon")
elif a=="3":
  print("bon")
else:
  print("hon")


### FIXED CODE ###

s =int( input()[-1])
if s in [2, 4, 5, 7, 9]:
  print('hon')
elif s in [0, 1, 6, 8]:
  print('pon')
else:
  print('bon')
S = input()
h = S/3600
m = (S - 3600*h)/60
s = S -3600*h -60*m
print h ":",
print m ":",
print s 

### FIXED CODE ###

S = input()
h = S/3600
m = (S - 3600*h)/60
s = S -3600*h -60*m
print "%d:%d:%d" %(h, m, s)
for i in range(L, R):
    for r in range(i+1, R+1):
        ans = (i*r) % 2019 
        if x > ans:
            x = ans
            if x == 0:
        	    break
    if x == 0:
      break

### FIXED CODE ###

L,R = map(int,input().split())
 
x = 2019**2
for i in range(L, R):
    for r in range(i+1, R+1):
        ans = (i*r) % 2019 
        if x > ans:
            x = ans
            if x == 0:
        	    break
    if x == 0:
      break
print(x)
a = int(input())

ans = a+a*2+a*3

print ans


### FIXED CODE ###

a = int(input())

ans = a+a*a+a*a*a

print(ans)
s=sorted(input())
s.replace(s[0],"").replace(s[2],"")

print(s)
                       

### FIXED CODE ###

c = 0 ; a = []

s = input()

for i in range(4):
    if s[i] not in  a:
        a.append(s[i])
    else:
        c += 1
    
if len(a) == 2 and c == 2:
    print('Yes')
else:
    print('No')
# -*- coding: utf-8 -*-
import sys
import copy
sys.setrecursionlimit(10000000)

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

L=[ [] for _ in range(H) ]
ng=[]

cnt=0
ichigo=False
for h in range(H):
    cnt+=1
    ichigo=False
    for w in range(W):
        if S[h][w]=="#":
            if ichigo:
                cnt+=1      ##該当行でイチゴの出現が2回目以降の時は、カウントを増やす
            else:
                ichigo=True #該当行でイチゴの出現が1回目の時はTrueを入れる
        L[h].append(cnt)
    else:
        if ichigo is False:
            ng.append(h) #イチゴが１つも入ってない行番号


memo=[]
def func(n,str):   #行番号 方向 u:up d:down
    #print "func(",n,",",str,")"
    if n in memo: return
    if n in ng:
        if 0<=n-1: func(n-1,"u")
        if n+1<=H-1: func(n+1,"d")
    else:      #NG行でない場合
        if str=="u":
                L[n+1]=copy.deepcopy(L[n])
                memo.append(n+1)
        elif str=="d":
                L[n-1]=copy.deepcopy(L[n])
                memo.append(n-1)
        return

#1行にイチゴが1つもない行に対して、前or後の行をコピーする処理
for x in ng:
    func(x,"u")
    func(x,"d")


#1,2,3...Kの順で再度ピースの番号を振り直す
D={}    #前のピース番号：後のピース番号のマッピング辞書配列

cnt=1
for h in range(H):
    for w,x in enumerate(L[h]):
        if x not in D:  #辞書内になかった場合は、辞書に登録してカウンターの数字を+1する
            D[x]=cnt
            L[h][w]=cnt
            cnt+=1
        else:
            L[h][w]=D[x]  #辞書内にあった場合は、その値を使用


for h in range(H):
    for x in L[h]:
        print x,
    print

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque,defaultdict
sys.setrecursionlimit(10**5)

H,W,K=map(int, sys.stdin.readline().split())
ichigo=[]
cnt=0
h_visit=[0 for h in range(H)]  #縦軸にイチゴがない箇所は0、ある箇所は1

L=[ [] for h in range(H) ]
for h in range(H):
    s=sys.stdin.readline().strip()
    for w,x in enumerate(s):
        if x==".":
            L[h].append(0)
        elif x=="#":
            cnt+=1
            L[h].append(cnt)
            ichigo.append((h,w))
            h_visit[h]=1


D=(1,-1)

def yoko_dfs(h,w):  #縦座標、横座標
    for dw in D:
        if 0<=w+dw<=W-1 and L[h][w+dw]==0:
            L[h][w+dw]=L[h][w]
            yoko_dfs(h,w+dw)
    return

for h,w in ichigo:
    yoko_dfs(h,w)


def tate_dfs(h):  #縦座標
    for dh in D:
        if 0<=h+dh<=H-1:
            if h_visit[h+dh]==1: continue
            h_visit[h+dh]=1 #訪問済みにする
            L[h+dh]=L[h]
            tate_dfs(h+dh)

for h,w in ichigo:
    tate_dfs(h)

for l in L:
    for x in l:
        print x,
    print
s=input()
A=list(s)
N=len(A)
M=N-1
k=0
while k<M/2:
  if A[k]!=A[M-k]:
    print("No")
  if A[k]!=A[(M-2)/2-k]:
    print("No")
  if A[k+M/2+1]!=A[M-k]:
    print("No")
  else:
    print("Yes")
  k=k+1

### FIXED CODE ###

import sys
L=list(input())
N=len(L)
R=N//2
for i in range(R):
  if L[i]!=L[N-1-i]:
    print("No")
    sys.exit()
  elif L[i]!=L[R-1-i]:
    print("No")
    sys.exit()
print("Yes")
if int(input()) <= 8 and int(input()) <= 8:
  print("Yay!")
else:
  print(":(")

### FIXED CODE ###

a, b = map(int, input().split())
if a <= 8 and b <= 8:
  print("Yay!")
else:
  print(":(")
N = int(input())
v = sorted(list(map(int,input().split())))
c = v[0]
for i in range(1,len(v)+1):
  c = (v[i]+c)/2
print(int(c))

### FIXED CODE ###

N = int(input())
v = sorted(list(map(int,input().split())))
c = v[0]
for i in range(1,len(v)):
  c = (v[i]+c)/2
print(c)
def f(n):
  for i in range(n):
    if i*(i+1)>=2*n:
      return(i)
      break
n=int(input())
Ans=[]
while n>1:
  Ans.append(f(n))
  n-=f(n)
Ans.append(1)
print(*Ans,sep="\n")

### FIXED CODE ###

n=int(input())
m=1
while m*(m+1)<2*n:
  m+=1
k=m*(m+1)//2-n
for i in range(m):
  if i+1==k:
    continue
  else:
    print(i+1)
from itertools import accumulate
n, k = map(int, input().split())
p = list(map(int, input().split()))
pex = [(1+n)/2 for n in p]
pex = list(accumulate(pex))
ans = []
for i in range(n-k):
    ans.append(pex[i+k] - pex[i])
print(max(ans))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
nxt = 0
mx = []
for i in range(n):
    pex = (1+p[i])/2
    mx.append(pex+nxt)
    nxt = pex + nxt
if n == k:
    print(mx[-1])
else:
    ans = []
    for i in range(n-k):
        ans.append(mx[i+k] - mx[i])
    print(max(ans))
a,b=[int(input())]
	if a!=2 and b!=2:
		print("Yes")
	else:
		print("No")

### FIXED CODE ###

a,b=map(int,input().split())
if a!=2 and b!=2:
	print("Yes")
else:
	print("No")
n=int(input())
s=n
temp=0
while s:
  temp=temp+s%10
  s=s//10
if n%s==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n=int(input())
s=n
temp=0
while s:
  temp=temp+s%10
  s=s//10
if n%temp==0:
  print("Yes")
else:
  print("No")
import numpy as np

def list753(n):
    if n == 1:
        return np.array([3,5,7],dtype=np.int)
    else:
        prev = list753(n-1)
        return np.concatenate((10*prev+3,10*prev+5,10*prev+7))

def all_list753(n):
    return np.concatenate(tuple([list753(i) for i in range(3,n+1)]))

Nstr = input()
N = int(Nstr)
Nlen = len(Nstr)

candidates = all_list753(Nlen)
ans = 0

for c in candidates:
    if c > N:
        continue
    cstr = str(c)
    if '3' in cstr and '5' in cstr and '7' in cstr:
        ans += 1

print(ans)

### FIXED CODE ###

import numpy as np

def count(n,s):
    if s == 0:
        return 3**n - 3*(2**n) + 3
    elif s == 1:
        return 3**n - 2**(n+1) + 1
    elif s == 2:
        return 3**n - 2**n
    else:
        return 3**n

def num753(Nlist, appeared):
    n = len(Nlist)
    if n == 0:
        if appeared == 7:
            return 1
        else:
            return 0
    
    top = Nlist[-1]
    
    ap3 = appeared|1
    s3 = ap3 % 2 + (ap3 % 4)//2 + ap3 // 4
    ap5 = appeared|2
    s5 = ap5 % 2 + (ap5 % 4)//2 + ap5 // 4
    ap7 = appeared|4
    s7 = ap7 % 2 + (ap7 % 4)//2 + ap7 // 4

    if appeared == 0:
        ans = sum([count(i,0) for i in range(3,n)])
    else:
        ans = 0

    if top < 3:
        pass
    elif top == 3:
        ans = ans + num753(Nlist[:-1],ap3)
    elif top == 4:
        ans = ans + count(n-1,s3)
    elif top == 5:
        ans = ans + count(n-1,s3) + num753(Nlist[:-1],ap5)
    elif top == 6:
        ans = ans + count(n-1,s3) + count(n-1,s5)
    elif top == 7:
        ans = ans + count(n-1,s3) + count(n-1,s5) + num753(Nlist[:-1],ap7)
    else: # top == 8,9
        ans = ans + count(n-1,s3) + count(n-1,s5) + count(n-1,s7)
    
    return ans

N = int(input())
Nlist=[]
while N > 0:
    Nlist.append(N % 10)
    N = N // 10
Nlist = np.array(Nlist,dtype=np.int)

print(num753(Nlist,0))
n, a, b, c, d = map(int, input().split())
s = [0 if i == "#" else 1 for i in input()]
if c < d:
    print("Yes")
    exit()
idx = b - 1
cnt = 0
while idx <= d + 1:
    if s[idx] == 0:
        cnt = 0
    else:
        cnt += 1
        if cnt == 3:
            print("Yes")
            exit()
    idx += 1
print("No")

### FIXED CODE ###

n, a, b, c, d = map(int, input().split())
s = input()
for i in range(a, max(c, d)):
    if s[i-1:i+1] == "##":
        print("No")
        exit()
if c < d:
    print("Yes")
    exit()
for i in range(b-1, d):
    if s[i-1:i+2] == "...":
        print("Yes")
        exit()
print("No")
import math

A,B,C,D=[int(x) for x in input().rstrip().split()]
cnt=0
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
baisuu=lcm(C,D)
yakusuu=math.gcd(C,D)

u_A=(A-1)-(A-1)//C-(A-1)//D+(A-1)//baisuu


u_B=B-B//C-B//D+B//baisuu
# for i in range(A,baisuu):
#   if i%C!=0 and i%D!=0:
#     cnt+=1

print(u_B-u_A)

### FIXED CODE ###

import fractions
from functools import reduce

A,B,C,D=[int(x) for x in input().rstrip().split()]
cnt=0

import math

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

    
baisuu=lcm(C,D)

u_A=(A-1)-(A-1)//C-(A-1)//D+(A-1)//baisuu

u_B=B-B//C-B//D+B//baisuu

print(u_B-u_A)
a, b = map(raw_input().split)

if a > b:
  print 'a > b'

elif a < b:
  print 'a < b'

else:
  print 'a == b'

### FIXED CODE ###

a,b = map(int, raw_input().split())
 
if a > b:
  print 'a > b'
 
elif a < b:
  print 'a < b'
 
else:
  print 'a == b'
A, B, C = map(int, input().split().split())

if A==B==C:
    print("no")
else:
    print("yes")

### FIXED CODE ###

a,b,c=map(int,input().split())

if a==b and a!=c:
    print("Yes")
elif a==c and a!=b:
    print("Yes")
elif b==c and b!=a:
    print("Yes")
else:
    print("No")
print("{}:{}:{}".format(input()/60, input/3600, input()%3600)

### FIXED CODE ###

i = int(input())
print("{}:{}:{}".format(int(i/(60*60)), int((i%(60*60))/(60)), i%60))
a,b=input(),split(' ')

print(a+' '+b)


### FIXED CODE ###

a,b = input().split()
a = int(a)
b = int(b)
S = a*b
C = 2 * (a+b)

print(str(S) + " " + str(C))
r=int(input())
g=int(input())
b=int(input())
num=100*r+10*g+b
if num%4==0:
    print("YES")
else:
    print("NO")
return 0

### FIXED CODE ###

r,g,b=(int(x) for x in input().split())

num=100*r+10*g+b
if num%4==0:
    print("YES")
else:
    print("NO")
A = int(input ())
B = int (input ())
if A > 8 or B > 8: 
    res = ‘: (‘

else:
    res = ‘Yay!’

print(res)

### FIXED CODE ###

ab = input()
a, b = ab.split()
A = int(a)
B = int (b)
if A > 8 or B > 8:
    res = ':('

else:
    res = 'Yay!'

print(res)
data = map(int, raw_input().split())
data = sorted(data)
data.reverse()

for i in range(3):
    print data[i]
    

### FIXED CODE ###

data = [0]

for i in range(10):
    data.append(int(input()))
    
data = sorted(data)
data.reverse()

for i in range(3):
    print data[i]
s = input()
a = []
for i in range(len(s)):
  a.append(s[i])
  

count = 0

for i in [0,3]:
  if a[i] == "1":
    count +=1
    
  
print(count)

### FIXED CODE ###

s = input()
 
x = 0
 
 
for i in range(len(s)):
  if s[i] == "1":
    x += 1
  
print(x)
from sys import exit
import fractions
n,m=map(int,input().split())
s=input()
t=input()


print((m*n)//gcd)


### FIXED CODE ###

from sys import exit
import math
from fractions import gcd

def lcm(x,y):
    return x*y//gcd(x,y)

N,M=map(int,input().split())
S=input()
T=input()
if S[0] != T[0]:
    print("-1")
    exit()
if N==M:
    if S==T:
        print(N)

    else:
        print(-1)
    exit()
    
if N<M:
    N,M=M,N
    S,T=T,S
    

# N>M S>T
if(N%M==0):
    S2=""
    for i in range(N):
        if i%(N//M)==0 :
            S2+=S[i]
            
    if S2==T:
        print(N)
    else:
        print(-1)
    exit()

else:
    g=gcd(N,M)
    S2=""
    for i in range(N):
        if i%(N//g)==0 :
            S2+=S[i]
    T2=""
    for i in range(M):
        if i%(M//g)==0 :
            T2+=T[i]
    if S2==T2:
        print(lcm(N,M))
    else:
        print(-1)
import numpy as np
import heapq
dif = 10 ** 6
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = np.full(n, initial_cost)
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, s)
    
    while(len(node_list) != 0 and len(serched_node) != n):
        index = int(heapq.heappop(node_list) % dif)
        if index in serched_node:
            continue
        serched_node.add(index)
        
        print(index)
        print(links)
        link = links[index]
        for j in link:
            if j in serched_node:
                continue
        
            cost = link_costs[index][j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, newcost * dif + j)
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = np.full((n, n), initial_cost)
links_cost_sn = np.full((n, n), initial_cost)

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links[u-1].add(v-1)
    links[v-1].add(u-1)
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)

trans = n - 1
costs = np.full(n, initial_cost)
for i in range(n - 1, -1, -1):
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if newcost < costs[trans]:
        trans = i
        costs[i] = newcost
        continue
    
    costs[i] = costs[trans]
    
for cost in costs:
    print(int(initial - cost))

### FIXED CODE ###

import heapq
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial] * n
    costs[s] = 0
    q = []
    heapq.heappush(q, (0, s))
    
    while(len(q) != 0):
        index_cost, index = heapq.heappop(q)
        if costs[index] < index_cost:
            continue

        for j in link_costs[index]:
            newcost = costs[index] + link_costs[index][j]
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(q, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links_cost_en = [{} for _ in range(n)]
links_cost_sn = [{} for _ in range(n)]

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    u -= 1
    v -= 1
    links_cost_en[u][v] = a
    links_cost_en[v][u] = a
    links_cost_sn[u][v] = b
    links_cost_sn[v][u] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)
cost_list = [cost_en_from_s[i] + cost_sn_to_t[i] for i in range(n)]

ans = [initial] * n
ans[-1] = cost_list[-1]
for i in list(range(n - 1))[::-1]:
    ans[i] = min(ans[i + 1], cost_list[i])
for i in range(n):
    print(initial - ans[i])
N, M = list(map(int, input().split()))
a = []
for _ in range(M):
    a.append(int(input()))
a = sorted(list(set(a)))
dif = [a[0]-1]
dif.extend([(a[i]-1)-(a[i-1]+1) for i in range(1,len(a))])
dif.extend([N-a[-1]-1])
max_dif = max(dif)
Fiblist = {-1:0,0:1,1:1,2:2}
for n in range(3,max_dif+1):
    Fiblist[n]=Fiblist[n-1]+Fiblist[n-2]
ans = 1
for part in dif:
    ans= ans*Fiblist[part]%1000000007
print(ans)

### FIXED CODE ###

N, M = list(map(int, input().split()))
a = []
for _ in range(M):
    a.append(int(input()))
a = sorted(list(set(a)))
if len(a)>0:
    dif = [a[0]-1]
    dif.extend([(a[i]-1)-(a[i-1]+1) for i in range(1,len(a))])
    dif.extend([N-a[-1]-1])
else:
    dif = [N]
max_dif = max(dif)
Fiblist = {-1:0,0:1,1:1,2:2}
for n in range(3,max_dif+1):
    Fiblist[n]=Fiblist[n-1]+Fiblist[n-2]
ans = 1
for part in dif:
    ans= ans*Fiblist[part]%1000000007
print(ans)
n=(input())
		a=0
		sum=1
		f=0
		f2=0
		for i in range(1,n):
			a=(input())
			if(a==0): 
				f2=1
			sum*=a
			if (sum>1000000000000000000):
				f=1;
		}
		if(f2==1): 
			print("0\n")
		else if(f==1):
			print("-1\n")
		else:
			print(sum)
			print("\n")

### FIXED CODE ###

N=int(input())
 
A=list(map(int,input().split()))
 
if 0 in A:
    print(0)
else:
    result=1
    for a in A:
        result=result*a
        if result>10**18:
            result=-1
            break
    print(result)
X, N = map(int, input().split())
p = list(map(int, input().split()))
p.sort()

if N == 0:
    print(X)
    exit()

i = 0
if X not in p:
    r = bisect_left(p, X)
    l = r-1
    if abs(p[l]-X) <= abs(p[r]-X):
        print(p[l])
    else:
        print(p[r])
else:
    i = 1
    while p[p.index(X)] + i in p:
        i += 1
    up = p[p.index(X)] + i
    
    i = 1
    while p[p.index(X)] - i in p:
        i += 1
    down = p[p.index(X)] - i

    if abs(down-X) <= abs(up-X):
        print(down)
    else:
        print(up)

### FIXED CODE ###

X, N = map(int, input().split())
p = list(map(int, input().split()))
p.sort()

if N == 0:
    print(X)
    exit()

if X not in p:
    print(X)    
else:
    i = 1
    while p[p.index(X)] + i in p:
        i += 1
    up = p[p.index(X)] + i
    
    i = 1
    while p[p.index(X)] - i in p:
        i += 1
    down = p[p.index(X)] - i

    if abs(down-X) <= abs(up-X):
        print(down)
    else:
        print(up)
N,M = map(int,input().split())
S = str(input())
SA = list(S)
D = ["a" , "b" , "c"]

if SA[M] == "A":
    SA[M] = D[0]
elif SA[M] == "B":
    SA[M] = D[1]
else:
    SA[M] = D[2]

M = ''.join(SA)

print(M)

### FIXED CODE ###

N,M = map(int,input().split())
S = str(input())
SA = list(S)
D = ["a" , "b" , "c"]

if SA[M-1] == "A":
    SA[M-1] = D[0]
elif SA[M-1] == "B":
    SA[M-1] = D[1]
elif SA[M-1] == "C":
    SA[M-1] = D[2]

M = ''.join(SA)

print(M)
import sys
sys.setrecursionlimit(10**9)
n=int(input())
t=[int(i) for i in sys.stdin]
def gcd(x,y):
  if y==0:
    return x
  return gcd(y,x%y)
x=t[0]
for i in range(1,n):
  y=x*t[i]//gcd(x,t[i])
  x=y
print(y)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
n=int(input())
t=[int(i) for i in sys.stdin]
if n==1:
  print(t[0])
  exit()
def gcd(x,y):
  if y==0:
    return x
  return gcd(y,x%y)
x=t[0]
for i in range(1,n):
  y=x*t[i]//gcd(x,t[i])
  x=y
print(y)
a,b=int(input().split())
if(a!=3 and b!=3):
  print(3)
elif(a!=2 and b!=2):
  print(2)
else:
  print(1)

### FIXED CODE ###

a=int(input())
b=int(input())
if a!=3 and b!=3:
  print(3)
elif a!=2 and b!=2:
  print(2)
else:
  print(1)
n = int(input()

a = list(map(int,input().split())))
if n ==len(set(a)):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if len(set(a)) == n:
    print("YES")
else:
    print("NO")
def factorial(n):
    res = 1
    for i in range(1, n+1):
        res *= i
    return res

n = int(input())
s = []
for i in range(n):
    s.append(list(str(input())))

for i in s:
    i.sort()

s.sort()

tmp = 'a'
total = 0
cnt = 1
for i in s:
    if i == tmp:
        cnt += 1
    elif cnt >= 2:
        total += factorial(cnt)*factorial(cnt-2)/2
        cnt = 1
    tmp = i
total += factorial(cnt)*factorial(cnt-2)/2

print(int(total))

### FIXED CODE ###

n = int(input())
ss = ["".join(sorted(list(input()))) for _ in range(n)]
ss.sort()

ans = 0
cnt = 0
tmp = ss.pop(0)
for s in ss:
    if tmp == s:
        cnt+=1
    elif cnt > 0:
        tmp = s
        ans+=((cnt+1) * cnt // 2)
        cnt = 0
    else:
        tmp = s
        cnt = 0
print(ans + ((cnt+1) * cnt // 2))