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

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


def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    
    
    s = ["#"*(w+4)]
    s.append("#"*(w+4))
    for i in range(h):
        s.append("##" + input().replace("\n", "") + "##")
    s.append("#"*(w+4))
    s.append("#"*(w+4))
    
    
    ans = [[-1]*(w+4) for _ in range(h+4)]
    for i in range(h+4):
        for j in range(w+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ans[ch][cw] = 0
    
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    not_yet = deque([(ch, cw)])
    one_time = deque([])
    
    while len(not_yet) > 0:
        x, y = not_yet.popleft()
        one_time.append((x, y))
        for (p, q) in move:
            if ans[x+p][y+q] == -1:
                not_yet.append((x+p, y+q))
                ans[x+p][y+q] = ans[x][y]
                
        if len(not_yet) == 0:
            while len(one_time) > 0:
                x2, y2 = one_time.popleft()
                for i in range(x2-2, x2+3):
                    for j in range(y2-2, y2+3):
                        if ans[i][j] == -1:
                            ans[i][j] = ans[x2][y2]+1
                            not_yet.append((i, j))
                            
                      
    print(ans[dh][dw])
    
    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

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


def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    
    s = [input().replace("\n", "") for _ in range(h)]
    
    ans = [[-1]*w for _ in range(h)]
    ans[ch-1][cw-1] = 0
    not_yet = deque([(ch-1, cw-1)])
    one_time = deque([])
    while not_yet:
        x, y = not_yet.popleft()
        one_time.append((x, y))
        if x > 0 and ans[x-1][y] == -1 and s[x-1][y] == ".":
            not_yet.append((x-1, y))
            ans[x-1][y] = ans[x][y]
        if x < h-1 and ans[x+1][y] == -1 and s[x+1][y] == ".":
            not_yet.append((x+1, y))
            ans[x+1][y] = ans[x][y]
        if y > 0 and ans[x][y-1] == -1 and s[x][y-1] == ".":
            not_yet.append((x, y-1))
            ans[x][y-1] = ans[x][y]
        if y < w-1 and ans[x][y+1] == -1 and s[x][y+1] == ".":
            not_yet.append((x, y+1))
            ans[x][y+1] = ans[x][y]
        if not not_yet:
            while one_time:
                x2, y2 = one_time.popleft()
                for i in range(max(0, x2-2), min(h, x2+3)):
                    for j in range(max(0, y2-2), min(w, y2+3)):
                        if ans[i][j] == -1 and s[i][j] == ".":
                            ans[i][j] = ans[x][y]+1
                            not_yet.append((i, j))

    print(ans[dh-1][dw-1])
            
            
            
        
    
    
    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
for i in range(2, N+1):
    t = 0
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t
K = N
ans = ""
while K > 0:
    for a in A:
        if K >= x[a] and dp[K] == dp[K-x[a]] + 1:
            if dp[K] == 1 and K != x[a]:
                continue
            ans += str(a)
            K -= x[a]
            break
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
INF = float('inf')
for i in range(1, N+1):
    t = -INF
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t

K = N
k = dp[N]
ans = ""
while k > 0:
    for a in A:
        xa = x[a]
        if K >= xa and k == dp[K-xa] + 1:
            ans += str(a)
            K -= xa
            k -= 1
            break
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i, item in enumerate(goods):
    i += 1
    for w in range(1, W+1):
        if w < item[0]:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-item[0]] + item[1])

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
INF = 10**12
goods = [tuple(map(int, input().split())) for _ in range(N)]
total_val = 0
for item in goods:
    total_val += item[1]
dp = [[INF for i in range(total_val+1)] for j in range(N+1)]
dp[0][0] = 0
for i, item in enumerate(goods):
    i += 1
    for v in range(total_val+1):
        if v < item[1]:
            dp[i][v] = dp[i-1][v]
        else:
            dp[i][v] = min(dp[i-1][v], dp[i-1][v-item[1]] + item[0])

for i in range(total_val+1):
    if dp[N][i] <= W:
        ans = i
print(ans)
### BUGGY CODE ###

N = int(input()) 
A=list(map(int,input().split())) 
i=0 
s=[]
sumall=0
for i in range(N):
    s.append(0) 
    s[i]=A.count(i+1)
    sumall=sumall+s[i]
    print(s[i])
    i=i+1
    if sumall>=N-1:
        break
for _ in range(i,N):
    print(0)

### FIXED CODE ###

import collections
n = int(input())
base = map(int,input().split())
c = collections.Counter(base)
for i in range(1,n):
    print(c[i])
print(0)
### BUGGY CODE ###

s=input()
m=[0]*(2019)
m[0]+=1

cnt = 0
b=0
for i in s[::-1]:
  a = (b + int(i)*10**cnt) % 2019
  m[a] += 1
  b = a
  cnt += 1


ans = 0
for i in m:
  if i <= 1:
    continue
  ans += i*(i-1)//2

print(ans)


### FIXED CODE ###

s=input()
ls=len(s)
m=[0]*(2019)
m[0]+=1

cnt = 0
b = 0
for i in range(ls):
  a = (b + pow(10,cnt,2019)*int(s[ls - i -1])) % 2019
  m[a] += 1
  b = a
  cnt += 1

ans = 0
for i in m:
  if i <= 1:
    continue
  ans += i*(i-1)//2

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

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

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

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(w, W+1):
        j = dp[i]
        if j == -1:
            continue
        if dp[i-w] < j + v:
            dp[i-w] = j + v

print(max(dp))


### FIXED CODE ###

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

N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

print(dp[-1])
### BUGGY CODE ###

n=int(input())
s=input()
r=[]
g=[]
b=[]
for i in range(n):
    if s[i]=="R":
        r.append(i+1)
    elif s[i]=="G":
        g.append(i+1)
    else:
        b.append(i+1)
cnt=0
sum=len(b)*len(g)*len(r)
if len(r)*len(g)*len(b)==0:
    print(0)
else:
    for re in r:
        for gr in g:
            
            re1=re
            re1,gr=min(re,gr),max(re,gr)
            #print(re,gr,b)
            if (re1+gr)%2==0:
                if (re1+gr)//2 in b:
                    cnt-=1
            if 2*gr-re1 in b:
                cnt-=1
            if 2*re1-gr in b:
                cnt-=1
            
            #print(cnt)
    print(sum+cnt)

### FIXED CODE ###

def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(map(str, input().split()))
def pl(a): print(" ".join(list(map(str, a))))
def ma():return map(int,input().split())
"""
k=ri()

n,k=ma()
for i in range(n):
    for

n=int(input())
s=input()
r=[0]*n
b=[0]*n
g=[0]*n

for i in range(n):
    if s[i]=="R":
"""

"""
from itertools import accumulate as acc
import operator as op
import copy as cp
import math; import numpy
from bisect import bisect_left as bisl
from bisect import bisect_right as bisr
###
"""



"""
import math
k=int(input())

cnt=0
for a in range(1,k+1):
    for b in range(1,k+1):
        ct=math.gcd(a,b)
        for c in range(1,k+1):
            cnt+=math.gcd(ct,c)

print(cnt)
"""
"""
n,k=map(int,input().split())
mod=10**9+7

import math
dj0=[[i for i in range(1,k+1)] for j in range(k)]
dj1=[i for i in range(1,k+1)]
dj2=[0]*k
for i in dj1:
    for j in range(1,k):
        dj0[i-1][j-1]=math.gcd(i,j)
        dj2[math.gcd(i,j)]+=1
"""
n=ri()
s=input()
ans = s.count("R")*s.count("G")*s.count("B")
for i in range(n):
    for j in range(i+1,n):
        k=2*j-i
        if k>=n:
            break
        ans-=s[k]!=s[i]!=s[j]!=s[k]

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

n,m = list(map(int,input().split()))
a = []
b = []
dic = {}
count = 0
"""
for i in range(n):
    x,y = list(map(int,input().split()))
    dic[x] = y
dic = sorted(dic.items())



for key in dic:
    if m - dic[key] > 0:
        count += key * dic[key]
        m = m - dic[key]
    else:
        count += m * key
        break
print(count)
"""
            



for i in range(n):
    x,y = list(map(int,input().split()))
    a.append(x)
    b.append(y)
count = 0


while m > 0:
    mi = min(a)
    d = a.index(mi)
    if m - b[d] > 0 : # Bi本買う
        m = m-b[d]
        count += b[d] * mi
    else:
        count += m * mi
        break
    del a[d]
    del b[d]
print(count)






### FIXED CODE ###

n,m = list(map(int,input().split()))
a = []
b = []
dic = {}
count = 0
data = [0] * n
for i in range(n):
    x,y = list(map(int,input().split()))
    data[i] = [x,y]
data = sorted(data,key = lambda x : x[0])
for i in range(n):
    if m > data[i][1]:
        count += data[i][0] * data[i][1]
        m -= data[i][1]
    else:
        count += data[i][0] * m
        break
print(count)

"""
for i in range(n):
    x,y = list(map(int,input().split()))
    dic[x] = y
dic = sorted(dic.items())



for key in dic:
    if m - dic[key] > 0:
        count += key * dic[key]
        m = m - dic[key]
    else:
        count += m * key
        break
print(count)
"""
            

"""

for i in range(n):
    x,y = list(map(int,input().split()))
    a.append(x)
    b.append(y)
count = 0


while m > 0:
    mi = min(a)
    d = a.index(mi)
    if m > b[d]  : # Bi本買う
        m -= b[d]
        count += b[d] * mi
    else:
        count += m * mi
        break
    del a[d]
    del b[d]
print(count)



"""
### BUGGY CODE ###

n=int(input())
ans = 0
for i in range(1, n+1):
    occ = int(n/i);
    val = int((occ * (occ+1))/2);
    ans += val*i;
print(ans)

### FIXED CODE ###

n=int(input())
ans = 0
for i in range(1, n+1):
    ans += (n//i) * ((n//i)+1)//2*i;
print(ans)
### BUGGY CODE ###

# D
N, K = list(map(int, input().split()))
p = list(map(int, input().split()))

for i in range(N):
    p[i] = (1+p[i])/2

ans = 0
for i in range(0, N-K+1):
    ans_tmp = sum(p[i:i+K])
    ans = max(ans, ans_tmp)
    
print(ans)


### FIXED CODE ###

# D

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

ans = sum(p[0:K])
ans_tmp = ans
for i in range(K, N):
#    print(p)
#    print(-p[i-K] + p[K])
    ans_tmp = ans_tmp - p[i-K] + p[i]
#    print(ans_tmp)
    ans = max(ans, ans_tmp)

ans = (ans+K)/2

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

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
for _ in range(m):
    b, c = map(int, input().split())
    a.extend([c] * b)
a = list(reversed(sorted(a)))
ans = sum(a[:n])
print(ans)

### FIXED CODE ###

import collections
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
k = collections.Counter(a)
for _ in range(m):
    b, c = map(int, input().split())
    k[c] += b
ans = 0
count = 0
for key in list(reversed(sorted(list(k.keys())))):
    ans += (min(k[key], n - count)) * key
    count += min(k[key], n - count)
    if count == n:
        break
print(ans)
### BUGGY CODE ###

import sys
import heapq
import collections

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

### FIXED CODE ###

from collections import*
from bisect import*
s=input()
n=len(s)
t=input()
d=defaultdict(list)
for i,c in enumerate(s):
    d[c].append(i)
m=-1
o=0
for c in t:
    if not d[c]:
        print(-1)
        exit()
    i=bisect(d[c],m)
    if len(d[c])==i:
        o+=1
        m=d[c][0]
    else:
        m=d[c][i]
print(o*n+m+1)
### BUGGY CODE ###

from collections import Counter

n = int(input())
lst = [input() for _ in range(n)]

counter_lst = []
counter_num = [0] * n
for i in range(n):
    a = Counter(lst[i])
    if a in counter_lst:
        m = counter_lst.index(a)
        counter_num[m] += 1
        counter_lst.append(0)
    else:
        counter_lst.append(a)
        counter_num[i] = 1
    
res = 0
for i in counter_num:
    if i > 0:
        res += i * (i-1) // 2
print(res)

### FIXED CODE ###

n = int(input())
lst = [input() for _ in range(n)]

dic = dict()
res = 0
for i in range(n):
    sorted_string = "".join(sorted(lst[i]))
    if sorted_string in dic:
        dic[sorted_string] += 1
        res += dic[sorted_string]
    else:
        dic[sorted_string] = 0
    
print(res)
### BUGGY CODE ###

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

mod = 10**9+7

all_num = k**n
ans = 0

dp = [0]*(k+1)

for i in range(k):
    tmp = k-i
    #print(tmp)
    #print(tmp,tmp,tmp)
    kazu = 1
    kakeru = 2
    heru = 0
    #print(tmp,k)
    while tmp * kakeru <= k:
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
        #print(tmp*kakeru,k)
        
    
    if tmp == 1:
        ans += all_num
        ans %= mod
        break
    ans += tmp*(kazu**n-heru)
    all_num -= (kazu**n-heru)
    #print(tmp,kazu,n,heru)
    dp[tmp] = kazu**n-heru
    ans %= mod
    #print(ans,tmp,kazu)
    
print(ans)

### FIXED CODE ###

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

mod = 10**9+7

all_num = pow(k,n,mod)
#all_num = k**n


ans = 0

dp = [0]*(k+1)

for i in range(k):
    tmp = k-i
    #print(tmp)
    #print(tmp,tmp,tmp)
    kazu = 1
    kakeru = 2
    heru = 0
    
    if tmp == 1:
        ans += all_num
        ans %= mod
        break
    
    #print(tmp,k)
    for i in range(k//tmp-1):
        #print(i)
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
    """
    while tmp * kakeru <= k:
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
        #print(tmp*kakeru,k)
    """ 
    
    kazu = pow(kazu,n,mod)-heru
    #kazu = kazu**n-heru
    ans += tmp*(kazu)
    all_num -= (kazu)
    #print(tmp,kazu,n,heru)
    dp[tmp] = kazu
    ans %= mod
    #print(ans,tmp,kazu)
    
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

M = 10**9+7

dp = [[1]*(m+1) for _ in range(n+1)]

for i in range(n):
  for j in range(m):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
    else:
      dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
    dp[i+1][j+1] %= M

#print(dp)
print(dp[-1][-1]%M)

### FIXED CODE ###

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

M = 10**9+7

dp = [[1]*(m+1) for _ in range(n+1)]

for i in range(n):
  for j in range(m):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
    else:
      dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
    dp[i+1][j+1] %= M

#print(dp)
print(dp[-1][-1]%M)
### BUGGY CODE ###

import bisect


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    tmp = 1
    while tmp * tmp <= n:
        if n % tmp == 0:
            lower_divisors.append(tmp)
            if tmp != n // tmp:
                upper_divisors.append(n // tmp)
        tmp += 1
    return lower_divisors + upper_divisors[::-1]


n = int(input())
*A, = map(int, input().split())
A.sort()
setA = set(A)
cnt = 0
for i, a in enumerate(A):
    if bisect.bisect_right(A, a) - bisect.bisect_left(A, a) != 1:
        cnt += 1
        continue
    X = set(make_divisors(a))
    if len(X & setA) != 1:
        cnt += 1
print(n - cnt)


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
maxA = max(A)
# C[a] = A内のaの個数
C = {a: 0 for a in range(1, maxA + 1)}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
D = {a: 0 for a in range(1, maxA + 1)}
for a in A:
    if C[a] > 0:
        tmp = 2
        while a * tmp <= maxA:
            D[a * tmp] = 1
            tmp += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

def main():
    ans = 0
    a,b = map(int,input().split())
    for x in range(a+1):
        for y in range(a+1):
            if x+y == b:
                ans += 1
            elif  x + y < b:
                for z in range(a+1):
                    if x + y + z == b:
                         ans += 1

    return ans

print(main())



### FIXED CODE ###

def main():
    ans = 0
    a,b = map(int,input().split())
    for x in range(a+1):
        for y in range(a+1):
            z = b-x-y
            if 0<=z and z<=a:
                ans += 1



    return ans

print(main())
### BUGGY CODE ###

N,Q = map(int, input().split())
S = input()
def judge_letter(letter, r, l):
    j_letter = letter[r-1 : l]
    return j_letter.count("AC")


for i in range(Q):
    l, r = map(int, input().split())
    print(judge_letter(S, l,r))

### FIXED CODE ###

import time
N,Q = map(int, input().split())
S = input()
AC = [0]*(N+1)

for i in range(N):
    if S[i:i+2] == "AC":
        AC[i+1] = AC[i] + 1
    else:
        AC[i+1] = AC[i]

for i in range(Q):
    l, r = map(int, input().split())
    print(AC[r-1] - AC[l-1])
### BUGGY CODE ###

import bisect
n = int(input())
nums = [int(input()) for i in range(n)]
count = 0
prevMaxs = []
for i in range(n):
    num = nums[i]
    if len(prevMaxs) == 0 :
        prevMaxs.append(num)
    else:
        key = bisect.bisect_left(prevMaxs, num)
        if key == 0:
            prevMaxs.insert(0, num)
        else:
            prevMaxs[key - 1] = num
print(len(prevMaxs))

### FIXED CODE ###

import sys
import bisect

n = int(input())
a = [int(sys.stdin.readline().rstrip()) for _ in range(n)][::-1]

bottoms = [a[0]]

for i in range(1, n):
    pos = bisect.bisect_right(bottoms, a[i])
    if pos == len(bottoms):
        bottoms.append(a[i])
    else:
        bottoms[pos] = a[i]

print(len(bottoms))
### BUGGY CODE ###

n=int(input())
s=input()
ans=[0]*1001
for i in range(1000):
    v=0
    i="000"+str(i)
    for j in s:
        if j==i[-1] and v==2:v+=1
        if j==i[-2] and v==1:v+=1
        if j==i[-3] and v==0:v+=1
    if v==3:ans[int(i)]=1
print(sum(ans))

### FIXED CODE ###

n=int(input())
s=input()
a,b,c=[],[],[]
ans=0
for i in range(n):
  if s[i] not in a:
    a.append(s[i])
    b=[]
    for j in range(i+1,n):
      if s[j] not in b:
        b.append(s[j])
        c=[]
        for k in range(j+1,n):
          if s[k] not in c:
            c.append(s[k])
            ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    if i*i <= N:
        ans = max(ans,i*i)
    #else:
        #break
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    if i*i <= N:
        ans = max(ans,i*i)
    else:
        break
print(ans)
### BUGGY CODE ###

import sys
from itertools import zip_longest
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[]
for i in range(m):
    b,c = map(int, input().split(" "))
    bc = bc + [c]*b
bc.sort(reverse=True)
print(sum(list(map(lambda x: x[1] if x[0] < x[1] else x[0], zip_longest(a,bc[0:n], fillvalue=0)))))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print(sum(a))
### BUGGY CODE ###

def green_bin(n,s):
    count = 0
    for i in range(n-1):
        si = sorted(s[i])
        for j in range(i+1,n):
            if i == j:
                continue
            else:
                sj = sorted(s[j])
            if si == sj:
                count += 1

    return count
if __name__ == '__main__':
    n = int(input())
    s = [ input() for i in range(n)]

    print(green_bin(n,s))

### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(raw_input())
d = {}
ans = 0
for i in range(n):
    si = ''.join(sorted(raw_input()))
    if si in d:
        ans += d[si]
        d[si] += 1
    else:
        d[si] = 1
print(ans)
### BUGGY CODE ###

l = list(map(int,input().split()))
a = l[0]
b = l[1]
x = l[2]
if a%x != 0:
	a = a+x-(a%x)
r =[i for i in range(a,b+1,x)]
print(len(r))


### FIXED CODE ###

l = list(map(int,input().split()))
a = l[0]
b = l[1]
x = l[2]
if a%x == 0:
	print(b//x-a//x +1)
else:
	print(b//x-a//x)
### BUGGY CODE ###

import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for _ in range(M)]

# 距離表の初期化
INF = 100# ** 12
dist = [[INF] * N for _ in range(N)]
for i in range(N):
	dist[i][i] = 0

# グラフを読み込みつつ距離表の更新
for a, b, c in ABC:
	a, b = a - 1, b - 1
	dist[a][b] = c
	dist[b][a] = c

# ワーシャル–フロイド法の前処理
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])

#print(dist)

# 全探索(*^_^*)つ[rCr]
min_dist = INF
for p in itertools.permutations(r):
	d = 0
	for n in range(1, R):
		d += dist[p[n] - 1][p[n - 1] - 1]
	if d < min_dist:
		min_dist = d
		#print(d, p)
print(min_dist)


### FIXED CODE ###

import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for _ in range(M)]

# 距離表の初期化
INF = 10 ** 12
dist = [[INF] * N for _ in range(N)]
for i in range(N):
	dist[i][i] = 0

# グラフを読み込みつつ距離表の更新
for a, b, c in ABC:
	a, b = a - 1, b - 1
	dist[a][b] = c
	dist[b][a] = c

# ワーシャル–フロイド法の前処理
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])

#print(dist)

# 全探索(*^_^*)つ[rCr]
min_dist = INF
for p in itertools.permutations(r):
	d = 0
	for n in range(1, R):
		d += dist[p[n] - 1][p[n - 1] - 1]
	if d < min_dist:
		min_dist = d
		#print(d, p)
print(min_dist)
### BUGGY CODE ###

from sys import stdin
X,Y,Z,K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
B = [int(x) for x in stdin.readline().rstrip().split()]
C = [int(x) for x in stdin.readline().rstrip().split()]

AB = []
for a in A:
    for b in B:
        AB.append(a+b)
        
AB.sort(reverse=True)
C.sort(reverse=True)
ABC = []

for ab in AB[:K]:
    for c in C[:K]:
        ABC.append(ab+c)
        
ABC.sort(reverse=True)

for abc in ABC[:K]:
    print(abc)

### FIXED CODE ###

from sys import stdin
X,Y,Z,K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
B = [int(x) for x in stdin.readline().rstrip().split()]
C = [int(x) for x in stdin.readline().rstrip().split()]

AB = []
for a in A:
    for b in B:
        AB.append(a+b)
        
AB.sort(reverse=True)
C.sort(reverse=True)
ABC = []

for ab in AB[:K]:
    for c in C[:K]:
        ABC.append(ab+c)
        
ABC.sort(reverse=True)

for abc in ABC[:K]:
    print(abc)
### BUGGY CODE ###

n = int(input())

power = 1
for i in range(1,n+1):
    power *= i

print(power%(10**9+7))


### FIXED CODE ###

n = int(input())

power = 1
for i in range(1,n+1):
    power *= i
    power = power%(10**9+7)
    
print(power)