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

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

R,G,B = [],[],[]

"""
for i in range(n):
    if n[i] == "R":
        R.append(i)
    elif n[i] == "G":
        G.append(i)
    else:
        B.append(i)
"""

ans = 0
for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            if s[i] != s[j] and s[i] != s[k] and s[k] != s[j]:
                if 2*j != i+k:
                    ans += 1

print(ans)

### FIXED CODE ###

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

R,G,B = [],[],[]


for i in range(n):
    if s[i] == "R":
        R.append(i)
    elif s[i] == "G":
        G.append(i)
    else:
        B.append(i)


base = len(R) * len(G) * len(B)

B = set(B)

ans = 0
for r in R:
    for g in G:
        y = max(r,g)
        x = min(r,g)
        
        # x < 0 < y

        tmp = int((x+y)/2)
        if (x+y)%2==0 and (tmp in B):
            ans += 1
        # x<y<0
        tmp = 2*y-x
        if tmp in B:
            ans += 1
        #0 < x < y
        tmp = 2*x-y
        if tmp in B:
            ans += 1

print(base-ans)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
P = []
for a in range(10):
  for b in range(10):
    #if a == 1:
      #print(P, ans)
    for c in range(10):
      P = []
      P.append(str(a))
      P.append(str(b))
      P.append(str(c))
      j = 0
      k = 0
      while j < len(P) and k < len(S):
        p = P[j]
        s = S[k]
        if p == s:
          j += 1
        k += 1
      if j == len(P):
        ans += 1
print(ans)

#print(*ans, sep='/n')

### FIXED CODE ###

n=int(input())
s=input()
ans=0
 
for i in range(10):
    for j in range(10):
        for k in range(10):
            x=s.find(str(i))
            if x!=-1:
                y=s.find(str(j),x+1)
                if y!=-1:
                    z=s.find(str(k),y+1)
                    if z!=-1:
                        ans+=1
print(ans)
### BUGGY CODE ###

V_TOTAL_MAX = 10 ** 5
INF = float('inf')

N, W = map(int, input().split())
dp = [[INF for _ in range(V_TOTAL_MAX + 1)] for _ in range(N + 1)]  # dp[品物番号][基準となる価値] = 重さの総和の最小値
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(0, V_TOTAL_MAX + 1):
        if j < v:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)

ans = 0
for j in range(0, V_TOTAL_MAX + 1):
    if dp[N][j] <= W:
        ans = max(ans, j)

print(ans)


### FIXED CODE ###

INF = 10 ** 12
MV = 10 ** 5

N, W = map(int, input().split())
dp = [[INF for _ in range(MV + 1)] for _ in range(N + 1)]
dp[0][0] = 0
# dp[品物のidx][価値の総和] = 実現する最小重量

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(MV + 1):
        if j - v >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
        else:
            dp[i][j] = dp[i - 1][j]

ans = -1
j = MV
while j >= 0:
    if dp[N][j] <= W:
        ans = j
        break
    j -= 1
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                cnt += 1
print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        if 0 <= s-x-y <= k:
            cnt += 1
print(cnt)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for i in range(0, k + 1):
    for j in range(0, k + 1):
        for l in range(0, k + 1):
            if i + j + l == s:
                count += 1

print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for i in range(k + 1):
    for j in range(k + 1):
        if 0 <= s - i - j <= k:
            count += 1

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

n,a=map(int,input().split())
x=list(map(int,input().split()))
s=n*a
dp=[[[0 for i in range(s+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0]=1
for i in range(n):
  for j in range(i+2):
    for k in range(s+1):
      if(k>=x[i]):
        dp[i+1][j][k]=dp[i][j-1][k-x[i]]+dp[i][j][k]
      else:
        dp[i+1][j][k]=dp[i][j][k]
outp=0
for i in range(1,n+1):
  outp+=dp[n][i][i*a]
print(outp)

### FIXED CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))
y=[]
for i in x:
  y.append(i-a)
s=2*n*a
dp=[[0 for i in range(s+1)] for j in range(n+1)]
dp[0][n*a]=1
for i in range(n):
  for j in range(s+1):
    x=j-y[i]
    if(0<=x and x<=2*n*a):
      dp[i+1][j]=dp[i][j-y[i]]+dp[i][j]
    else:
      dp[i+1][j]=dp[i][j]

print(dp[n][n*a]-1)
### BUGGY CODE ###

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 10**9 + 7

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

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

print(dp[n][m])


### FIXED CODE ###

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 10**9 + 7

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

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

print(dp[n][m])
### BUGGY CODE ###

n = int(input())
s = list(map(int, input().split()))
count = 0
for i in range(n):
  for j in range(i, n):
    if sum(s[i:j+1])==0:
      count+=1

print(count)

### FIXED CODE ###

n = int(input())
s = list(map(int, input().split()))
count = 0
dic = {}
cl = []
sm = 0
for i in range(n):
  sm+=s[i]
  if sm not in dic.keys():
    dic.update({sm:1})
  else:
    dic[sm]+=1

        
for x in dic.keys():
  t = dic[x]
  if x==0:
    count+=dic[x]
  count+=int(t*(t-1)/2)

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

a,b,k=map(int,input().split())
a_st=a
b_st=b
num=[]
cnt=0
for i in range(a,b+1):
    if cnt<k:
        num.append(i)
        cnt+=1
cnt=0
for i in range(b,a,-1):
    if cnt<k:
        num.append(i)
        cnt+=1
num2=list(set(num))
num2.sort()
[print(x) for x in num2]

### FIXED CODE ###

a,b,k=map(int,input().split())
a_st=a
b_st=b
num=[]
cnt=0
for i in range(a,b+1):
    if cnt<k:
        num.append(i)
        cnt+=1
    else:
        break
cnt=0
for i in range(b,a,-1):
    if cnt<k:
        num.append(i)
        cnt+=1
    else:
        break
num2=list(set(num))
num2.sort()
[print(x) for x in num2]
### BUGGY CODE ###

# ABC133E - Virus Tree 2
from collections import deque


def main():
    N, K, *AB = map(int, open(0).read().split())
    MOD = 10 ** 9 + 7
    G = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(AB)] * 2):
        G[v].append(u), G[u].append(v)
    queue = deque([1])
    seen = [0] * (N + 1)
    seen[1] = 1
    ans, cand = K, K - 1
    while queue:
        v = queue.popleft()
        for u in G[v]:
            if not seen[u]:
                seen[u] = 1
                ans = (ans * cand) % MOD
                cand -= 1
                queue.append(u)
        if sum(seen) == N:
            break
        cand = K - 2
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ABC133E - Virus Tree 2
from collections import deque


def main():
    N, K, *AB = map(int, open(0).read().split())
    MOD = 10 ** 9 + 7
    G = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(AB)] * 2):
        G[v].append(u), G[u].append(v)
    queue = deque([1])
    seen = [0] * (N + 1)
    seen[1] = 1
    ans, cand = K, K - 1
    while queue:
        v = queue.popleft()
        for u in G[v]:
            if not seen[u]:
                seen[u] = 1
                ans = (ans * cand) % MOD
                cand -= 1
                queue.append(u)
        cand = K - 2
    print(ans)


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

n = int(input())
ans = 0
for i in range(1, n):
    for j in range(1,n):
        if (n - i) % j == 0:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1, n):
    ans += (n - 1) // a
print(ans)
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline
num = int(input())
word_list = []
for i in range(num):
    word_list.append(input())
word_dict = collections.Counter(word_list)
word_list = [k for k,v in word_dict.items() if v == word_dict.most_common()[0][1]]
word_list.sort()
for word in word_list:
    print(word)

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline
num = int(input())
word_list = []
for i in range(num):
    word_list.append(input())
word_dict = collections.Counter(word_list)
most_common = word_dict.most_common()[0][1]
word_list = [k for k,v in word_dict.items() if v == most_common]
word_list.sort()
for word in word_list:
    print(word)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = []
    queue = deque()

    for i in range(H):
        isVisited.append([-1]*W)
        st = input()
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j,0))

    answer = 0
    a =  [(0,1),(1,0),(-1,0),(0,-1)]
    while queue:
        i,j,count = queue.popleft()

        if isVisited[i][j] == -1:
            isVisited[i][j] = count
            if count>answer:
                answer = count
            for ix,iy in a:
                if 0<=i+ix<H and 0<=j+iy<W:
                    queue.append((i+ix,j+iy,count+1))
 
    print(answer)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[False]*W for _ in range(H)]
    queue = deque()

    for i in range(H):
        st = input()
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j))

    answer = 0
    a =  [(0,1),(1,0),(-1,0),(0,-1)]
    while True:
        nqueue = deque()
        while queue:
            i,j = queue.popleft()

            if not isVisited[i][j]:
                isVisited[i][j] = True
                for ix,iy in a:
                    if 0<=i+ix<H and 0<=j+iy<W:
                        nqueue.append((i+ix,j+iy))
        
        if nqueue:
            answer += 1
            queue = nqueue
        else:
            break
 
    print(max(answer-1,0))
    return

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

import fractions
import sys
from functools import reduce
import math

input = sys.stdin.readline


def main():
    n, m = input_list()
    starts = []
    ends = []
    for _ in range(m):
        a, b = input_list()
        if a == 1:
            starts.append(b)
        elif b == n:
            ends.append(a)
    s = list(sorted(starts))
    e = list(sorted(ends))
    for a in s:
        if a in e:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')

def get_camulative(l):
    import itertools
    # 累積和
    return [0] + list(itertools.accumulate(l))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


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


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

s = []
e = []
for _ in range(m):
  a, b = map(int, input().split())
  if a == 1:
    s.append(b)
  if b == n:
    e.append(a)

if set(s) & set(e):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

import itertools
import math

def func(x,y,z):
    return x**2+y**2+z**2+x*y+y*z+z*x
 
n = int(input())
s = int(math.sqrt(n))
nums = list(range(1,s))
arr = []
com = list(itertools.product(nums, repeat=3))
for i in range(len(com)):
    # print(com)
    # ans = func(com[i][0],com[i][1],com[i][2])
    ans = com[i][0]**2+com[i][1]**2+com[i][2]**2+com[i][0]*com[i][1]+com[i][1]*com[i][2]+com[i][0]*com[i][2]
    arr.append(ans)
 
for i in range(n):
    print(arr.count(i+1))

### FIXED CODE ###

import itertools
import math
import collections
def main():
    n = int(input())
    s = int(math.sqrt(n))
    a = list(itertools.product(range(1,s),repeat=3))
    ans = []
    for i in range(len(a)):
        t = a[i][0] ** 2 + a[i][1] ** 2 + a[i][2] ** 2 + a[i][0] * a[i][1] + a[i][1] * a[i][2] + a[i][2] * a[i][0]
        ans.append(t)
        # print(ans)
    c = collections.Counter(ans)
    for i in range(1,n+1):
        print(c[i])
        
        
main()
### BUGGY CODE ###

S=list(input())
Q=int(input())
r=1
for i in range(Q):
    T=input().split()
    if T[0]=="1":
        r*=-1
        continue
    if T[1]=="1":
        if r==1:
            S=[T[2]]+S
        else:
            S=S+[T[2]]
        continue
    if r==1:
        S=S+[T[2]]
    else:
        S=[T[2]]+S
if r==1:
    print("".join(S))
else:
    print("".join(list(reversed(S))))

### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
r=1
for i in range(Q):
    T=input().split()
    if T[0]=="1":
        r*=-1
        continue
    t=T[2]
    if T[1]=="1":
        if r==1:
            S.appendleft(t)
        else:
            S.append(t)
        continue
    if r==1:
        S.append(t)
    else:
        S.appendleft(t)
if r==1:
    print("".join(list(S)))
else:
    S.reverse()
    print("".join(list(S)))
### BUGGY CODE ###

n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")

nxt = [i for i in range(n+10)]
for i in range(1, n+10):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	if x == 1<<(n-1-i):
		print(0)
		continue
	if s[i] == "0":
		tmp = (x + pow(2, n-1-i, p+1)) % (p+1)
	else:
		tmp = (x - pow(2, n-1-i, p-1)) % (p-1)
	ans = 1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")
if p > 1:
	pre0 = x%(p-1)
pre1 = x%(p+1)

nxt = [i for i in range(n+10)]
for i in range(1, n+10):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	if x == 1<<(n-1-i):
		print(0)
		continue
	if s[i] == "0":
		tmp = (pre1 + pow(2, n-1-i, p+1)) % (p+1)
	else:
		tmp = (pre0 - pow(2, n-1-i, p-1)) % (p-1)
	ans = 1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
data = []
for i in range(m):
    data.append(list(map(int, input().split())))
num = 1
count = 0
while num <= n:
    flag = True
    for i in range(m):
        if data[i][0] > num or data[i][1] < num:
            flag = False
    num += 1
    if flag:
        count += 1
print(count)

### FIXED CODE ###

n, m = list(map(int, input().split()))
data = []
data1 = []
data2 = []
for i in range(m):
    data.append(list(map(int, input().split())))
for i in range(m):
    data1.append(data[i][0])
    data2.append(data[i][1])
if min(data2) - max(data1)  + 1 > 0:
    print(min(data2) - max(data1) + 1)
else:
    print(0)
### BUGGY CODE ###

from fractions import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans+=gcd(i,gcd(j,l))
print(ans)

### FIXED CODE ###

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)
### BUGGY CODE ###

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


dp = [[[-1.0 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(N + 1)]


def solve(n1, n2, n3):

    if dp[n1][n2][n3] >= 0.0:
        return dp[n1][n2][n3]
    if n1 == n2 == n3 == 0:
        return 0.0

    cnt = n1 + n2 + n3
    ret = 0
    if n3 >= 1:
        ret += solve(n1, n2 + 1, n3 - 1) * n3
    if n2 >= 1:
        ret += solve(n1 + 1, n2 - 1, n3) * n2
    if n1 >= 1:
        ret += solve(n1 - 1, n2, n3) * n1

    ret = (ret + N) / cnt
    dp[n1][n2][n3] = ret
    return ret


a1, a2, a3 = 0, 0, 0
for i in range(N):
    if A[i] == 1:
        a1 += 1
    elif A[i] == 2:
        a2 += 1
    elif A[i] == 3:
        a3 += 1

print(solve(a1, a2, a3))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

def diameter(N, E):#diamete of a tree
    V = [-1]*N
    V[0] = 0
    q = [0]
    s = 0
    while q:
        v = q.pop(0)
        for w in E[v]:
            if V[w] == -1:
                s = w
                V[w] = V[v] + 1
                q.append(w)
    # s = V.index( max(V))
    p = [s]
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.pop(0)
        for w in E[v]:
            if W[w] == -1:
                W[w] = W[v] + 1
                p.append(w)
    return max(W)

N = int( input())
E = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    E[a].append(b)
    E[b].append(a)
ans = "First"
if diameter(N, E)%3 == 1:
    ans = "Second"
print( ans)

### FIXED CODE ###

from collections import deque
def diameter(N, E):#diamete of a tree
    V = [-1]*N
    V[0] = 0
    q = deque([0])
    s = 0
    while q:
        v = q.popleft()
        for w in E[v]:
            if V[w] == -1:
                s = w
                V[w] = V[v] + 1
                q.append(w)
    # s = V.index( max(V))
    p = deque([s])
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.popleft()
        for w in E[v]:
            if W[w] == -1:
                W[w] = W[v] + 1
                p.append(w)
    return max(W)

N = int( input())
E = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    E[a].append(b)
    E[b].append(a)
ans = "First"
if diameter(N, E)%3 == 1:
    ans = "Second"
print( ans)
### BUGGY CODE ###

from collections import deque
def main():
    N,M = map(int,input().split())
    G = [deque([]) for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    stack = deque([0])
    sign = [0] * N
    while stack:
        v = stack.popleft()
        for w in G[v]:
            if sign[w] == 0 and not w in stack:
                sign[w] = v+1
                stack.append(w)   

    sign = sign[1:]
    if all(s > 0 for s in sign):
        print('Yes')
        for s in sign:
            print(s)
    else:
        print('No')
        
main()

### FIXED CODE ###

from collections import deque
def main():
    N,M = map(int,input().split())
    G = [deque([]) for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    stack = deque([0])
    sign = [0] * N
    while stack:
        v = stack.popleft()
        for w in G[v]:
            if sign[w] == 0:
                sign[w] = v+1
                stack.append(w)   

    sign = sign[1:]
    if all(s > 0 for s in sign):
        print('Yes')
        for s in sign:
            print(s)
    else:
        print('No')
        
main()
### BUGGY CODE ###

def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(a-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num * pow(den,c-2,c) % c
mod = 10**9 + 7
n,k = map(int,input().split())
inv = [0,1]
for i in range(2,n):
  inv += [inv[mod % i]*(mod - mod//i) % mod]
a = list(map(int,input().split()))
a.sort()
ans = 0
c = cmb(n-1,k-1,mod)
if k == 1:
    print(0)
    exit()
for i in range(n-k+1):
    ans -= a[i] * c
    ans += a[-i-1] * c
    ans %= mod
    c = c*(n-k-i)*inv[n-i-1]
if ans < 0:
    ans += mod
print(ans)

### FIXED CODE ###

def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(a-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num * pow(den,c-2,c) % c
mod = 10**9 + 7
n,k = map(int,input().split())
inv = [0,1]
for i in range(2,n):
  inv += [inv[mod % i]*(mod - mod//i) % mod]
a = list(map(int,input().split()))
a.sort()
ans = 0
c = 1
x = 1
if k == 1:
    print(0)
    exit()
for i in range(n-k+1):
    ans -= a[n-k-i] * c
    ans += a[k+i-n-1] * c
    ans %= mod
    c = c*(i+k)*inv[i+1] % mod
if ans < 0:
    ans += mod
print(ans)
### BUGGY CODE ###

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

if n%2!=0:
    for i in range(n):
        if i%2==0:
            b.insert(0,a[i])
        else:
            b.append(a[i])
else:
    for i in range(n):
        if i%2!=0:
            b.insert(0,a[i])
        else:
            b.append(a[i])
print(" ".join(b))
#TLE


### FIXED CODE ###

n=int(input())
a=list(input().split())
b1=[]
b2=[]
if n%2==0:
    for i in range(n):
        if i%2!=0:
            b1.append(a[n-i])
        else:
            b2.append(a[i])
else:
    for i in range(n):
        if i%2==0:
            b1.append(a[n-1-i])
        else:
            b2.append(a[i])

b1.extend(b2)

print(" ".join(b1))
### BUGGY CODE ###

H,W = map(int,input().split())
S = [input() for _ in range(H)]
left = [[0]*W for _ in range(H)]
right = [[0]*W for _ in range(H)]
up = [[0]*W for _ in range(H)]
down = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if(S[i][j]=="."):
            if(j == 0):
                left[i][j] = 1
            else:
                left[i][j]=left[i][j-1]+1
for i in range(H):
    for j in range(W):                
        if(S[i][W-j-1]=="."):
            if(j == 0):
                right[i][W-j-1]=1
            else:
                right[i][W-j-1]=right[i][W-j]+1
for i in range(H):
    for j in range(W):                   
        if(S[i][j]=="."):
            if(i == 0):
                up[i][j] = 1
            else:
                up[i][j]=up[i-1][j]+1
for i in range(H):
    for j in range(W):     
        if(S[H-i-1][j]=="."):
            if(i == 0):
                down[H-i-1][j]=1
            else:
                down[H-i-1][j]=down[H-i][j]+1
ans = 0
X = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        X[i][j] = left[i][j]+right[i][j]+up[i][j]+down[i][j]-3
    ans = max(ans,max(X[i]))
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [input() for _ in range(H)]
left = [[0]*W for _ in range(H)]
right = [[0]*W for _ in range(H)]
up = [[0]*W for _ in range(H)]
down = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if(S[i][j]=="."):
            if(j == 0):
                left[i][j] = 1
            else:
                left[i][j]=left[i][j-1]+1
for i in range(H):
    for j in range(W-1,-1,-1):                
        if(S[i][j]=="."):
            if(j == W-1):
                right[i][j]=1
            else:
                right[i][j]=right[i][j+1]+1
for i in range(H):
    for j in range(W):                   
        if(S[i][j]=="."):
            if(i == 0):
                up[i][j] = 1
            else:
                up[i][j]=up[i-1][j]+1
for i in range(H-1,-1,-1):
    for j in range(W):     
        if(S[i][j]=="."):
            if(i == H-1):
                down[i][j]=1
            else:
                down[i][j]=down[i+1][j]+1
ans = 0
X = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        X[i][j] = left[i][j]+right[i][j]+up[i][j]+down[i][j]-3
    ans = max(ans,max(X[i]))
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(1, n+1):
    ans *= i

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

### FIXED CODE ###

import math
n = int(input())
ans = math.factorial(n)

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