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

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def main():
    N = NI()
    P = primes(N)
    D = [1] * (N+1)
    for p in P:
        for i in range(1, N//p + 100):
            d = p * i
            if d > N:
                break

            tmp = 0
            while d % p == 0:
                tmp += 1
                d = d // p
            D[p*i] *= tmp + 1

    ans = 0
    for i, d in enumerate(D):
        ans += i * d
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def main():
    N = NI()


    def num_divisors_table(n):
        table = [0] * (n + 1)

        for i in range(1, n + 1):
            for j in range(i, n + 1, i):
                table[j] += 1

        return table
    D = num_divisors_table(N)
    ans = 0
    for i in range(1, N+1):
        ans += D[i] * i
    print(ans)

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

import math
ans = 0

K = int(input())

for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans += math.gcd(i,math.gcd(j,k))
      
print(ans)

### FIXED CODE ###

import math
ans = 0

K = int(input())

for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans += math.gcd(i,math.gcd(j,k))
      
print(ans)
### BUGGY CODE ###

import heapq

n, m = list(map(int, input().split()))
cards = list(map(int, input().split()))
heapq.heapify(cards)
queries = []
for i in range(m):
    q = list(map(int, input().split()))
    queries.append(q)

for q in queries:
    b, c = q
    cnt = 0
    while cnt < b:
            heapq.heappushpop(cards, c)
            cnt += 1

ans = 0
for i in range(n):
    ans += cards[i]

print(ans)


### FIXED CODE ###

import heapq

n, m = list(map(int, input().split()))
cards = list(map(int, input().split()))
cards.sort()

queries = []
for i in range(m):
    q = list(map(int, input().split()))
    queries.append(q)
queries.sort(key=lambda x: x[1])
queries.reverse()

ans = 0
pos = 0
for q in queries:
    b, c = q
    if cards[min(pos+b-1, n-1)] < c:
        # print('a')
        pos = pos + b
        ans += c * (b - max(0, pos-n))
        if pos >= n:
            break
    else:
        for i in range(b):
            if cards[pos+i] < c:
                # print('b')
                ans += c
            else:
                # print('c')
                pos += i
                for j in range(pos, n):
                    ans += cards[j]

                pos = n
                break
        break

if pos < n:
    for j in range(pos, n):
        ans += cards[j]

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

K = int(input())
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        r = a%b
        a = b
        b = r
    return a
count = 0
temp = list()
for n in range(1, K+1):
    for m in range(1, K+1):
        temp.append(gcd(n, m))
for l in range(1, K+1):
    for j in range(len(temp)):
        p = gcd(l, temp[j])
        count += p
print(count)

### FIXED CODE ###

K = int(input())
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        r = a%b
        a = b
        b = r
    return a
count = 0
temp = list()
for n in range(1, K+1):
    for m in range(1, n):
        temp.append(gcd(n, m))
for l in range(1, K+1):
    for j in range(len(temp)):
        p = gcd(l, temp[j])
        count += 2 * p
    for k in range(1, K+1):
        q = gcd(l, k)
        count += q
print(count)
### BUGGY CODE ###

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

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


def main():
    import sys
    input = sys.stdin.readline
    s = input().rstrip("\n")
    q= int(input())
    han=0
    
    for i in range(q):
        que=input().split()
        if len(s)==1 and que[0]=="1":
            continue

        if que[0]=="1":
            han+=1
            #print(han, s, que)
        else:
            if han%2==0:#反転なし
                if que[1]=="1":
                    s=que[2]+s
                else:
                    s+=que[2]
            else:#あり
                if que[1] == "1":
                    s+=que[2]
                else:
                    s=que[2]+s
            #print(han, s, que)

    if han%2==0:
        print(s)
    else:
        print(s[::-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


def main():
    import sys
    input = sys.stdin.readline
    s = input().rstrip("\n")
    q = int(input())
    
    qq = [input().split() for i in range(q)]
    cnt=0
    r=""
    l=""
    #print(qq)
    for que in qq:
        if que[0] == "1":
            #print("a")
            r,l=l,r
            cnt+=1
            #print(r,l,cnt)
        else:
            if que[1] == "1":
                l+=que[2]
            else:
                r+=que[2]
            #print(r,l, que)
    #print(r,l)
    if cnt%2==0:
        print(l[::-1]+s+r)
    else:
        print(l[::-1]+s[::-1]+r)



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

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
a.sort()
b = []
ans = n

for i in a:
    for p in range(len(b)):
        j,k = b[p]
        if i%j == 0:
            ans -= 1
            if i == j and k == 0:
                ans -= 1
                b[p] = (j,1)
            break
    else:
        b.append((i,0))

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
a.sort()
b = [0]*1000001

s = set()

for i in a:
    if b[i]:
        continue
    if i in s:
        b[i] = 1
    s.add(i)
    for j in range(2, 1000001):
        if i*j > 10 ** 6:
            break
        b[i*j] = 1

ans = 0
for i in a:
    if b[i] == 0:
        ans += 1

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy


def main():
  r, c = map(int, input().split())
  g = [[1 if v == '.' else 0 for v in input().strip()] for _ in range(r)]
  v = numpy.zeros((2, r, c), dtype=numpy.int)

  for y in range(r):
    s = 0
    for x in range(c):
      if g[y][x] == 0:
        v[0, y, s:x] = x - s
        s = x + 1

    v[0, y, s:] = c - s

  for x in range(c):
    s = 0
    for y in range(r):
      if g[y][x] == 0:
        v[1, s:y, x] = y - s
        s = y + 1

    v[1, s:, x] = r - s

  v = v[0] + v[1]

  print(numpy.max(v) - 1)


if __name__ == '__main__':
  main()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy


def main():
  r, c = map(int, input().split())
  g = numpy.array([[1 if v == '.' else 0 for v in input().strip()] for _ in range(r)])
  g = numpy.array([g, g])

  for x in range(1, c):
    g[0, :, x] += g[0, :, x] * g[0, :, x - 1]

  for x in range(c - 2, -1, -1):
    g[0, :, x] = (g[0, :, x] != 0) * numpy.maximum(g[0, :, x], g[0, :, x + 1])

  for y in range(1, r):
    g[1, y] += g[1, y] * g[1, y - 1]

  for y in range(r - 2, -1, -1):
    g[1, y] = (g[1, y] != 0) * numpy.maximum(g[1, y], g[1, y + 1])

  g = g[0] + g[1]

  print(numpy.max(g) - 1)


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

N=int(input())
G=[]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u-=1;v-=1
    G.append([u,v,w])
G.sort()
col=[-1 for i in range(N)]
col[0]=0

from collections import deque
G=deque(G)

while len(G)>0:
    e=G.popleft()
    if col[e[0]]!=-1:
        col[e[1]]=(e[2]+col[e[0]])%2
    elif col[e[1]]!=-1:
        col[e[0]]=(e[2]+col[e[1]])%2
    else:
        G.append(e)

for i in col:
    print(i)

### FIXED CODE ###

N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u-=1; v-=1; w%=2
    G[u].append([v,w])
    G[v].append([u,w])
col=[-1 for i in range(N)]
col[0]=0

from collections import deque
dq=deque([0])

while len(dq)>0:
    p=dq.popleft()
    for i in range(len(G[p])):
        if col[G[p][i][0]]==-1:
            dq.append(G[p][i][0])
            col[G[p][i][0]]=(col[p]+G[p][i][1])%2
        
for i in col:
    print(i)
### BUGGY CODE ###

n,m=map(int,input().split())
a = [list(map(int,input().split())) for i in range(m)]
c = [x for x in a if x[0] == 1 or x[1] == n]
d = [z[0] for z in c if z[1] == n ]
ans = [z for z in c if z[0] == 1 and z[1] in d ]
print('IMPOSSIBLE' if len(ans) == 0 else 'POSSIBLE')

### FIXED CODE ###

n,m=map(int,input().split())
lst = set()
fst = set()
for i in range(m): 
  r = list(map(int,input().split()))
  if r[1] == n:
    lst.add(r[0])
  elif r[0] == 1:
    fst.add(r[1])
print('IMPOSSIBLE' if len(fst & lst) == 0 else 'POSSIBLE')
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

# min
min_ = 0
for n in range(N-K+1):
    min_ += A[n]*cmb(N-1-n, K-1)

# max
max_ = 0
for n in reversed( range(K-1, N) ):
    max_ += A[n]*cmb(n, K-1)

mod = 10**9+7
print( (max_-min_)%mod )


### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N_ = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N_ + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

# min
min_ = 0
for n in range(N-K+1):
    min_ += A[n]*cmb(N-1-n, K-1, mod)

# max
max_ = 0
for n in reversed( range(K-1, N) ):
    max_ += A[n]*cmb(n, K-1, mod)

#mod = 10**9+7
print( (max_-min_)%mod )
### BUGGY CODE ###

#ALDS1_5-B Merge Sort
from collections import deque

def merge(A,B):
    ans = deque()
    count = 0
    while(True):
        if len(A)==0 and len(B) == 0:
            break
        elif len(A) == 0:
            ans.append(B.popleft())
        elif len(B) == 0:
            ans.append(A.popleft())
        elif A[0] > B[0]:
            ans.append(B.popleft())
        else:
            ans.append(A.popleft())
        count+=1
    return (ans.copy(),count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.pop()
    if(len(d)>2):
        mid = len(d)//2
        div.appendleft(d[:mid])
        div.appendleft(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.appendleft(d[::-1])
        else:
            mer.appendleft(d)
        count+=2
    else:
        mer.appendleft(d)
        
while(len(mer)>1):
    A = deque(mer.popleft())
    B = deque(mer.popleft())
    ret = merge(A,B)
    mer.append(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)


### FIXED CODE ###

from collections import deque

def merge(A,B):
    ans = [0]*(len(A)+len(B))
    count=i=j=0
    A+=[10**9+1]
    B+=[10**9+1]
    for k in range(len(ans)):
        if A[i]<B[j]:
            ans[k]=A[i]
            i+=1
        else:
            ans[k]=B[j]
            j+=1
        count+=1
    return (ans,count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.popleft()
    if(len(d)>2):
        mid = len(d)//2
        div.append(d[:mid])
        div.append(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.append(d[::-1])
        else:
            mer.append(d)
        count+=2
    else:
        mer.append(d)
        
while(len(mer)>1):
    A = mer.pop()
    B = mer.pop()
    ret = merge(A,B)
    mer.appendleft(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)
### BUGGY CODE ###

S = input()
leng = len(S)

count = [0] * 2019
count[0] = 1

for i in range(leng):
    remainder = int(S[i:]) % 2019
    count[remainder] += 1

res = 0
for cnt in count:
    res += cnt * (cnt - 1) // 2
    
print(res)

### FIXED CODE ###

s = input()[::-1]

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

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

def solve():
    n = int(input())
    s = input()
    q = int(input())
    ks = list(map(int, input().split()))

    for k in ks:
        ans = 0
        cnt = 0
        d = 0
        m = 0
        for i in range(n):
            if s[i] == 'D':
                d += 1
            elif s[i] == 'M':
                m += 1
                cnt += d
            elif s[i] == 'C':
                ans += cnt

            if i >= k - 1:
                if s[i - k + 1] == 'D':
                    cnt -= m
                    d -= 1
                elif s[i - k + 1] == 'M':
                    m -= 1

        print(ans)


if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    n = int(input())
    s = input()
    q = int(input())
    ks = list(map(int, input().split()))

    for k in ks:
        ans = 0
        cnt = 0
        d = 0
        m = 0
        for i in range(n):
            if s[i] == 'D':
                d += 1
            elif s[i] == 'M':
                m += 1
                cnt += d
            elif s[i] == 'C':
                ans += cnt

            if i >= k - 1:
                if s[i - k + 1] == 'D':
                    cnt -= m
                    d -= 1
                elif s[i - k + 1] == 'M':
                    m -= 1

        print(ans)


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

import copy
S = input()
#print(S)
S2 = S.replace("BC", "D")
#print(S2)
S3 = []
s4 = ""
flag = 0
for i in range(len(S2)):
    #print(S2[i])
    if S2[i] == "A" or S2[i] == "D":
        s4 = s4 + S2[i]
        flag = 1
    elif flag == 1:
        S3.append(s4)
        s4 = ""
        flag = 0
    #print(S3)
    #print(s4)
S3.append(s4)
#print(S3)
count  = 0
for i in S3:
    for j in range(len(i) - 1, -1, -1):
        #print(i[j], j, count)
        if i[j] == "D":
            for k in range(j, -1, -1):
                if i[k] == "A":
                    count += 1

print(count)

### FIXED CODE ###

import copy
S = input()
#print(S)
S2 = S.replace("BC", "D")
#print(S2)
count = 0
Acount = 0
Dcount = 0
for i in range(len(S2)):
    if S2[i] == 'A' or S2[i] == 'D':
        if S2[i] == 'A':
            Acount += 1
        else:
            count += Acount
    else:
        Acount = 0
    #print(count, Acount, S2[i])
print(count)
### BUGGY CODE ###

import numpy as np

def count_num_light(a):
  ret = np.array([0 for _ in range(len(a))])
  for i in range(len(a)):
    start = max(0, i-a[i])
    ret[start:i+a[i]+1] += 1
  
  return ret
                  
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
num_light = count_num_light(a)

for i in range(k-1):
  num_light = count_num_light(num_light)

print(*num_light)

### FIXED CODE ###

def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  n = len(a)
  for i in range(n):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < n:
      ret[end+1] -= 1
  for i in range(1,n):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if sum(num_light) == n**2:
    break
    
print(*num_light)
### BUGGY CODE ###

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

import math
s=0
R=int(p)

dic = {}

while s==0:
    for i in range(2,R+1):
        if p%i==0:
            if i not in dic.keys():
                dic[i] = 0
            p = p//i
            if p==1:
                s=1
            dic[i] += 1
            break
out=1
for i in dic.keys():
    if dic[i] >=n:
        out *= i**(dic[i]//n)

print(out)

### FIXED CODE ###

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

if n==1:
    print(p)
else:
    out=1
    tm = int(pow(p, 1/n))
    for i in range(2,tm+1):
        while p%(i**n)==0:
            p = p//(i**n)
            out *= i
        if p < i**n:
            break
    print(out)
### BUGGY CODE ###

N,C = map(int,input().split())
T = [[0 for i in range(10**5+1)] for j in range(30)]

for i in range(N):
    s,t,c = map(int,input().split())
    T[c-1][s] += 1
    T[c-1][t] -= 1
for i in range(C):
    for j in range(10**5):
        T[i][j+1] += T[i][j]

for i in range(C):
    for j in range(10**5):
        if T[i][-j-1] == 0 and T[i][-j-2] == 1:
            T[i][-j-1] = 1
ans = 0
for i in range(10**5+1):
    ans = max(ans,sum(T[j][i] for j in range(C)))
print(ans)

### FIXED CODE ###

N,C = map(int,input().split())
T = [[0 for i in range(10**5+1)] for j in range(30)]

for i in range(N):
    s,t,c = map(int,input().split())
    T[c-1][s] += 1
    T[c-1][t] -= 1
for i in range(C):
    for j in range(10**5):
        T[i][j+1] += T[i][j]

for i in range(C):
    for j in range(10**5):
        if T[i][-j-1] == 0 and T[i][-j-2] == 1:
            T[i][-j-1] = 1
ans = 0
for i in range(10**5+1):
    ans = max(ans,sum(T[j][i] for j in range(C)))
print(ans)
### BUGGY CODE ###

import sys #追加
sys.setrecursionlimit(10**6) 

n,q = map(int,input().split())
from collections import defaultdict
dic = defaultdict(list)
for _ in range(n-1):
    a,b = map(int,input().split())
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)

from collections import defaultdict
dicp = defaultdict(int)

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


ansl = [0 for i in range(n)]
used = [0 for i in range(n)]
def dfs(pos, point):
    point += dicp[pos]
    used[pos] = 1
    ansl[pos] = point
    for p in dic[pos]:
        if used[p] == 0:
            dfs(p, point)

dfs(0, 0)

for a in ansl:
    print(a)

### FIXED CODE ###

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

from collections import defaultdict
dic = defaultdict(int)
for _ in range(q):
   p,x = map(int,input().split())
   dic[p-1] += x

ans = [0 for i in range(n)]
ans[0] = dic[0]

used = [0 for i in range(n)]
used[0] = 1
quu = [0]
while quu:
   k = quu.pop()
   for l in m[k]:
      if used[l] == 0:
         used[l] = 1
         quu.append(l)
         ans[l] = ans[k] + dic[l]

for i in ans:
   print(i)
### BUGGY CODE ###

# O(N^2)?
N = int(input())
A = [int(x) for x in input().split()]


for i in range(N):
    reg = 0
    B = A[:i] + A[i+1:]
    reg += abs(B[0]) + abs(B[-1])
    for j in range(N-2):
        reg += abs(B[j]-B[j+1])
    print(reg)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
A = [0] + A + [0]

S = 0
for i in range(len(A) - 1):
    S += abs(A[i] - A[i+1])
for i in range(1, len(A)-1):
    reg = S - abs(A[i-1] - A[i]) - abs(A[i] - A[i+1]) + abs(A[i-1] - A[i+1])
    print(reg)
### BUGGY CODE ###

#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)

S_ = np.array(S)

def count_answer(x,y,num_b,num_w):
    # print(used)

    if S_[x][y] == "#":
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S_[next_x][next_y] != S_[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S_[i,j] == "#":
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)


### FIXED CODE ###

#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)


def count_answer(x,y,num_b,num_w):
    # print(used)

    if S[x][y] == "#":
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S[next_x][next_y] != S[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S[i][j] == "#":
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)
### BUGGY CODE ###

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

### FIXED CODE ###

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