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

n=int(input())
s=list(input())
b=[]
for i in range(1000):
	while len(str(i))<3:
		i="0"+str(i)
	for j in range(n):
		if str(i)[0]==s[j]:
			for k in range(j+1,n):
				if str(i)[1]==s[k]:
					for l in range(k+1,n):
						if str(i)[2]==s[l]:
							b.append(i)
							break
					break
			break
print(len(set(b)))

### FIXED CODE ###

n=int(input())
s=list(input())
counter=0
for i in range(1000):
	while len(str(i))<3:
		i="0"+str(i)
	i=str(i)
	if i[0] in s:
		a=s.index(i[0])
		if i[1] in s[a+1:]:
			b=s[a+1:].index(i[1])+a+1
			if i[2] in s[b+1:]:
				counter+=1
print(counter)
### BUGGY CODE ###

def main(N, A):
    ans = 0
    for i in range(N-1):
        for j in range(i+1, N):
            ans += A[i]*A[j]
            ans = ans % (10**9 + 7)
    return ans

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    ans = main(N, A)
    print(ans)



### FIXED CODE ###

def main(N, A):
    ans = 0
    culm = sum(A)
    for i in range(N-1):
        culm -= A[i]
        ans += A[i]*culm
        ans %= 10**9 + 7
    return ans

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    ans = main(N, A)
    print(ans)
### BUGGY CODE ###

N = int(input())
problem = [int(input()) for _ in range(N)]

def dsf(i, sum):
    if i == N:
        if sum % 10 == 0:
            return 0
        else:
            return sum
    return max(dsf(i + 1, sum), dsf(i + 1, sum - problem[i]))

if sum(problem) % 10 != 0:
    print(sum(problem))
else:
    print(dsf(0, sum(problem)))

### FIXED CODE ###

N = int(input())
problem = [int(input()) for _ in range(N)]
memo = [[-1] * (sum(problem) + 1)] * N
def dsf(i, sum):
    if i == N:
        if sum % 10 == 0:
            return 0
        else:
            return sum
    if memo[i][sum] != -1: return memo[i][sum]
    else:
        memo[i][sum] = max(dsf(i + 1, sum), dsf(i + 1, sum - problem[i]))
        return memo[i][sum]

if sum(problem) % 10 != 0:
    print(sum(problem))
else:
    print(dsf(0, sum(problem)))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split())) 
c = 0
for i in range(n):
  for j in range(i+1, n):
    if max(i-j, j-i) == a[i]+a[j]:
      c +=1
print(c)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
# a+i と i-aのとりうる値の個数をカウントするが
# 一致するとしても[0, n)の範囲だけなのでDの大きさはnで十分
D = [0]*n
for i, a in enumerate(A):
    if 1+i+a < n:
        D[i+a] += 1
ans = 0
# i-aに対応するD[i-a]を加えるだけで答えが求まる
for i, a in enumerate(A):
    if 1+i-a >= 0:
        ans += D[i-a]
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline
N,a_,b_=map(int,input().split())
l=[min(a_,N-a_),min(b_,N-b_)]
a=min(l)
b=max(l)
#print(a,b)
cmb=1
mod=10**9+7
for i in range(1,a+1):
    cmb*=N-(a-i)
    cmb=cmb//i
    cmb=cmb%mod
ans=-1-cmb
for i in range(a+1,b+1):
    cmb*=N-(b-i)
    cmb=cmb//i
    cmb=cmb%mod

ans-=cmb

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x
ans+=pow_k(2,N)
print(ans%mod)

### FIXED CODE ###

# coding: utf-8
n,a_,b_=map(int,input().split())
l=[min(a_,n-a_),min(b_,n-b_)]
a,b=min(l),max(l)
mod=10**9+7
def pow_k(x,n):
    k=1
    #kは漏れたやつ
    while n>1:
        if n%2==1:
            k*=x
            n-=1
            k=k%mod
        x**=2
        x=x%mod
        n//=2
    
    return (k * x) % mod
    
#ans=pow_k(2,1000000000)
def modcomb(n,r,mod):
    X, Y =  1, 1
    r = min(r, n-r)
    for i in range(1,r+1):
        X = X * (n-i+1) % mod
        Y = Y * i % mod
    
    return (X * pow_k(Y, mod-2) % mod) % mod
ans=pow_k(2,n)-1-modcomb(n,a,mod)-modcomb(n,b,mod)
print(ans%mod)
### BUGGY CODE ###

N, M, QNUM = [int(x) for x in input().split()]

L = [None] * M
R = [None] * M

for i in range(M):
    l, r = [int(x) for x in input().split()]
    L[i] = l
    R[i] = r

P = [None] * QNUM  # P
Q = [None] * QNUM  # Q

for i in range(QNUM):
    p, q = [int(x) for x in input().split()]
    P[i] = p
    Q[i] = q

T = [[0] * (N + 1) for _ in range((N + 1))]

for i in range(M):
    for s in range(1, L[i] + 1):
        for e in range(R[i], N + 1):
            T[s][e] += 1


for i in range(QNUM):
    print(T[P[i]][Q[i]])


### FIXED CODE ###

N, M, QN = [int(x) for x in input().split()]

MAT0 = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(M):
    l, r = [int(x) for x in input().split()]
    MAT0[l][r] += 1

MAT = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        MAT[i][j] = MAT[i][j - 1] + MAT0[i][j]

MM = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        MM[i][j] = MM[i - 1][j] + MAT[i][j]

for i in range(QN):
    p, q = [int(x) for x in input().split()]
    ret = 0
    ret = ret + MM[q][q] - MM[q][p - 1] - MM[p - 1][q] + MM[p - 1][p - 1]
    print(ret)
### BUGGY CODE ###

from collections import defaultdict

n,m=map(int,input().split())
inf=[]
pre=defaultdict(list)
for _ in range(m):
    p,y=map(int,input().split())
    pre[p-1].append(y)
    inf.append([p,y])
for key,lis in pre.items(): pre[key]=sorted(lis)
for i in inf: print("{:06}{:06}".format(i[0],1+pre[i[0]-1].index(i[1])))

### FIXED CODE ###

n,m=map(int,input().split())
pre=[[] for _ in range(n)]
for _ in range(m):
    p,y=map(int,input().split())
    pre[p-1].append([y,_,p])
for p in range(n):
    pre[p].sort(key=lambda x:x[0])
    for i in range(len(pre[p])):
        pre[p][i].append(i)
lis=[]
for i in pre:
    for j in i:
        lis.append(j)
lis.sort(key=lambda x:x[1])
for i in lis: print("{:06}{:06}".format(i[2],i[3]+1))
### BUGGY CODE ###

from collections import deque
from bisect import bisect

S = input()
if len(S) < 4:
  print(0)
else:
  N = len(S)
  ans = 0
  for i in range(N):
    cnt = 0
    for j in range(i+4, N+1):
      ans += 1 if int(S[i:j])%2019 == 0 else 0
  print(ans)



### FIXED CODE ###

S = input()
if len(S) < 4:
  print(0)
else:
  N = len(S)
  x = 0
  d = [0]*2019
  d[0] = 1
  for i, s in enumerate(reversed(S)):
    x = (x+int(s)*pow(10,i,2019))%2019
    d[x] += 1
  print(sum([m*(m-1)//2 for m in d]))
### BUGGY CODE ###

N = int(input())
X = list(input())

def popcount(n):
    return bin(n).count('1')
memo = {1:1}
def f_count(n):
    co_n = n
    ans = 0
    while n != 0:
        if n in memo:
            ans += memo[n]
            memo[co_n] = ans
            return ans
        n %= popcount(n)
        ans += 1
    memo[co_n] = ans
    return ans

for i in range(N):
    co_x = X.copy()
    if co_x[i] == "1":
        co_x[i] = "0"  
    else:
        co_x[i] = "1"
    num = int("".join(co_x), 2)
    print(f_count(num))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
one_mod, zero_mod = 0, 0

for b in X:
    if one_pop != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop

pop = {0:0}
def popcount(n):
    if n in pop:
        return pop[n]
    pop[n] = popcount(n // 2) + n % 2
    return pop[n]
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return memo[n]
one_p = {0:1}
def one_pow(n):
    if n in one_p:
        return one_p[n]
    one_p[n] = one_pow(n - 1) * 2 % one_pop
    return one_p[n]
zero_p = {0:1}
def zero_pow(n):
    if n in zero_p:
        return zero_p[n]
    zero_p[n] = zero_pow(n - 1) * 2 % zero_pop
    return zero_p[n]
for i in range(N):
    if X[i] == '1' and one_pop == 0:
        print(0)
        continue
    if X[i] == '1':
        x = one_mod
        x -= one_pow(N-1-i)
        x %= one_pop
    elif X[i] == '0':
        x = zero_mod
        x += zero_pow(N-1-i)
        x %= zero_pop
    
    print(f_count(x) + 1)
### BUGGY CODE ###

s = input()
a = int(s)%2019
mods = [0]*2019
mods[a] += 1
d = 10**(len(s)-1)
for i in s:
  a = (a-int(i)*d)%2019
  d = d//10
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import numpy as np
N, K=map(int, input().split())
P=np.array(list(map(int, input().split())))

best=0
bestP=[0]*K
for i in range(N-K+1):
  if P[i:i+K].sum()>best:
    best=P[i:i+K].sum()
    bestP=P[i:i+K]
    

print(((bestP+1)/2).sum())

### FIXED CODE ###

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

#n面サイコロの出る目の期待値
def n_mean(n):
  return 0.5*(n+1)

Pmean=list(map(lambda x: n_mean(x), P))
Psum=[0]*N
Psum[0]=Pmean[0]
for i in range(1,N):
  Psum[i]=Psum[i-1]+Pmean[i]
#print(Psum)
ans=0
for i in range(N-K+1):
  if i==0:
    ans=Psum[K-1]
  else:
    #1~6 
    ans=max(ans, (Psum[i+K-1]-Psum[i-1]))
  
print(ans)
### BUGGY CODE ###

N=int(input())

A=[]

for i in range(N):
	ai=int(input())
	if ai in A:
		A.remove(ai)
	else:
		A.append(ai)
print(len(A))

### FIXED CODE ###

N=int(input())

A=[int(input()) for i in range(N)]
A.sort()
ans=N

flag=False

for i in range(N-1):
	if flag==True:
		flag=False
		continue
	elif A[i]==A[i+1]:
		ans-=2
		flag=True
#print(A)
print(ans)
### BUGGY CODE ###

# @author 

import sys

class JSushi:
    def solve(self):
        n = int(input())
        a = [int(_) for _ in input().split()]

        u, v, w = a.count(1), a.count(2), a.count(3)

        dp = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]
        for k in range(n + 1):
            for j in range(n + 1):
                for i in range(n + 1):
                    if i == j == k == 0:
                        continue
                    s = i + j + k
                    x = 0
                    x += dp[i][j + 1][k - 1] * k
                    x += dp[i + 1][j - 1][k] * j
                    x += dp[i - 1][j][k] * i
                    x += n
                    x /= s
                    dp[i][j][k] = x

        print(dp[u][v][w])


solver = JSushi()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class JSushi:
    def solve(self):
        n = int(input())
        a = [int(_) for _ in input().split()]

        u, v, w = a.count(1), a.count(2), a.count(3)

        dp = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]
        for k in range(n + 1):
            for j in range(n + 1 - k):
                for i in range(n + 1 - j - k):
                    if i == j == k == 0:
                        continue
                    s = i + j + k
                    x = 0
                    x += dp[i][j + 1][k - 1] * k
                    x += dp[i + 1][j - 1][k] * j
                    x += dp[i - 1][j][k] * i
                    x += n
                    x /= s
                    dp[i][j][k] = x

        print(dp[u][v][w])


solver = JSushi()
input = sys.stdin.readline

solver.solve()
### BUGGY CODE ###

n = int(input())
temparr = input()
temparr = temparr.split()
arr = []
for i in temparr:
    arr.append(int(i))
    
ans = 0 
for i in range(n - 1):
    curnum = arr[i]
    for j in range(i + 1, n):
        ans += curnum * arr[j]
        if ans >= 1000000007:
            ans -= 1000000007

if ans >= 1000000007:
    print(ans % 1000000007)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
temparr = input()
temparr = temparr.split()
arr = []
for i in temparr:
    arr.append(int(i)  % 1000000007)
    
ans = 0 
total = []
curtotal = sum(arr)
total.append(curtotal)
for i in range(n):
    curtotal -= arr[i]
    total.append(curtotal)
for i in range(n):
    total[i] = total[i] % 1000000007

for i in range(n - 1):
    curnum = arr[i]
    tempans = curnum * total[i + 1]
    if tempans >= 1000000007:
        tempans = tempans % 1000000007
    ans += tempans

if ans >= 1000000007:
    print(ans % 1000000007)
else:
    print(ans)
### BUGGY CODE ###

def resolve():
    t = input()
    ans = ''
    for c in t:
        if c == '?':
            ans += 'D'
        else:
            ans += c

    print(ans)

resolve()

### FIXED CODE ###

def resolve():
    t = input()
    ans = []
    is_pre_p = False
    for c in t:
        if c == '?':
            ans.append('D')
        else:
            ans.append(c)

    print("".join(ans))

resolve()
### BUGGY CODE ###

def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a%b)
N=int(input())
s=0
for i in range(1,N+1):
  for j in range(1,N+1):
    for h in range(1,N+1):
      a=gcd(i,j)
      s+=gcd(a,h)
print(s)

### FIXED CODE ###

def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a%b)
N=int(input())
s=0
for i in range(1,N+1):
  for j in range(i+1,N+1):
    for h in range(j+1,N+1):
      a=gcd(i,j)
      s+=6*gcd(a,h)
for p in range(1,N+1):
  for q in range(1,N+1):
    if p==q:
      s+=p
    else:
      s+=3*gcd(p,q)
print(s)
### BUGGY CODE ###

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
    
def UF_check(root,x,y):
    if find_root(root,x) == find_root(root,y):
        return True
    else:
        return False
    
def UF_make(graph,n):  #グラフと最大項を与えると、塊ごとにグルーピングする
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):  #これを入れれば、UF_checkを使わずに一塊になる
        Root[i] = find_root(Root,i)
    Root.pop(0)  #
    return Root

N,M=map(int,input().split())
P=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]

UF=UF_make(XY,N)
#print(UF)

groups=[[] for i in range(N+1)]
for i in range(N):
    groups[UF[i]].append(P[i])

#print(groups)
ans=0
for i in range(N):
    if i+1 in groups[UF[i]]:
        ans+=1

print(ans)

### FIXED CODE ###

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
    
def UF_check(root,x,y):
    if find_root(root,x) == find_root(root,y):
        return True
    else:
        return False
    
def UF_make(graph,n):  #グラフと最大項を与えると、塊ごとにグルーピングする
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):  #これを入れれば、UF_checkを使わずに一塊になる
        Root[i] = find_root(Root,i)
    Root.pop(0)  #
    return Root

N,M=map(int,input().split())
P=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]

UF=UF_make(XY,N)
#print(UF)

groups=[[] for i in range(N+1)]
for i in range(N):
    groups[UF[i]].append(P[i])

for i in range(N+1):
    groups[i].sort()

import bisect
ans=0
for i in range(N):
    num=bisect.bisect_left(groups[UF[i]],i+1)
    if num!=len(groups[UF[i]]) and groups[UF[i]][num]==i+1:
        ans+=1

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

K = int(input())

t = 7
ans = 1

for _ in range(K):
    if t % K == 0:
        print(ans)
        exit(0)
    else:
        t = t * 10 + 7
        ans += 1

print(-1)

### FIXED CODE ###

K = int(input())

t = 7
ans = 1

for _ in range(K):
    if t % K == 0:
        print(ans)
        exit(0)
    else:
        t = (t * 10 + 7) % K
        ans += 1

print(-1)
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for i in range(M)]
A.sort(key=lambda x:-x)
BC.sort(key=lambda x:x[1])
B = []
while len(B) < N and BC:
    b,c = BC.pop()
    B = [c]*b + B
B = B[-N:]
ans = 0
for i in range(len(B)):
    a = A.pop()
    b = B.pop()
    ans += max(a,b)
ans += sum(A)
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for i in range(M)]
A.sort(key=lambda x:-x)
BC.sort(key=lambda x:x[1])
C = []
while BC and len(C) < N:
    b,c = BC.pop()
    for i in range(b):
        C.append(c)
        if len(C) == N:
            break
C.sort()
ans = 0
while C:
    a = A.pop()
    c = C.pop()
    ans += max(a,c)
ans += sum(A)
print(ans)
### BUGGY CODE ###

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

# In[12]:


import collections


# In[10]:


N = int(input())
s = []
for _ in range(N):
    s.append(input())


# In[18]:


ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        if collections.Counter(s[i]) == collections.Counter(s[j]):
            ans += 1
print(ans)



### FIXED CODE ###

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

# In[12]:


import collections


# In[10]:


N = int(input())
s = []
for _ in range(N):
    s.append(input())


# In[30]:


ans = 0
mydict = {}
for i in range(N):
    tmp = "".join(sorted(s[i]))
    if tmp not in mydict:
        mydict[tmp] = 1
    else:
        ans += mydict[tmp]
        mydict[tmp] += 1
print(ans)
### BUGGY CODE ###

import math
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
    return primes
primes = primes(10**5)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in primes:
        if (i+1)//2 in primes:
            cnt += 1
    dp[i] = cnt

    
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(dp[r]-dp[l-2])

### FIXED CODE ###

import math
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
    return primes
primes = primes(10**5)
anss = []
for p in primes:
    if (p+1)//2 in primes:
        anss.append(p)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in anss:
        cnt += 1
    dp[i] = cnt

    
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(dp[r]-dp[l-2])
### BUGGY CODE ###

def bfs(start, goal, maze, visited):
    queue = [start]
    visited[start[0]][start[1]] = True
    dist = {(start[0], start[1]): 0}
    while queue:
        y, x = queue.pop(0)
        if y == goal[0] and x == goal[1]:
            return dist[(y, x)]
        for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            x_, y_ = x + i, y + j
            if y_ >= 0 and y_ < h and x_ >= 0 and x_ < w and maze[y_][x_] == "." and not visited[y_][x_]:
                queue.append((y_, x_))
                visited[y_][x_] = True
                dist[y_, x_] = dist[y, x] + 1


h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
max_dist = 0
for sy in range(h):
    for sx in range(w):
        for gy in range(h):
            for gx in range(w):
                if maze[sy][sx] == "." and maze[gy][gx] == ".":
                    visited = [[False for _ in range(w)] for _ in range(h)]
                    max_dist = max(max_dist, bfs(
                        (sy, sx), (gy, gx), maze, visited))
print(max_dist)


### FIXED CODE ###

def bfs(start, maze, visited):
    queue = [start]
    visited[start[0]][start[1]] = True
    dist = {(start[0], start[1]): 0}
    max_dist = 0
    while queue:
        y, x = queue.pop(0)
        for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            x_, y_ = x + i, y + j
            if y_ >= 0 and y_ < h and x_ >= 0 and x_ < w and maze[y_][x_] == "." and not visited[y_][x_]:
                queue.append((y_, x_))
                visited[y_][x_] = True
                dist[y_, x_] = dist[y, x] + 1
                max_dist = max(max_dist, dist[y_, x_])
    return max_dist


h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
max_dist = 0
for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] == ".":
            visited = [[False for _ in range(w)] for _ in range(h)]
            max_dist = max(max_dist, bfs((sy, sx), maze, visited))
print(max_dist)
### BUGGY CODE ###

N = int(input().strip())

x, y, z = 1, 1, 1

f = []
for i in range(N+1):
    f.append(set())

# while x**2 + y**2 + z**2 + x*y + y*z + x*z <= N:
def calc(x, y, z, f, a=0, b=0, c=0, axis=""):
    # print(x, y, z)
    if axis == "":
        ns = [x**2, y**2, z**2, x*y, y*z, x*z]
    elif axis == "x":
        ns = [x**2, a, b, x*y, c, x*z]
    elif axis == "y":
        ns = [a, y**2, b, x*y, y*z, c]
    elif axis == "z":
        ns = [a, b, z**2, c, y*z, x*z]
    else:
        ns = []
    # n = (x+y+z) ** 2 - (x*y + y*z + x*z)
    n = 0
    for i in range(6):
        n += ns[i]

    if n <= N:
        f[n].add("%d-%d-%d" % (x, y, z))
        # print(n, x, y, z)
        f = calc(x+1, y, z, f, a=ns[1], b=ns[2], c=ns[4], axis="x")
        f = calc(x, y+1, z, f, a=ns[0], b=ns[2], c=ns[5], axis="y")
        f = calc(x, y, z+1, f, a=ns[0], b=ns[1], c=ns[3], axis="z")
        return f
    else:
        return f

f = calc(x, y, z, f)
# while True:
#     f = calc(x, y, z, f)
#     f = calc(x+1, y, z, f)
#     f = calc(x, y+1, z, f)
#     f = calc(x, y, z+1, f)
#     f = calc(x+1, y+1, z, f)
#     f = calc(x, y+1, z+1, f)
#     f = calc(x+1, y, z+1, f)
#
#     x += 1
#     y += 1
#     z += 1
#
#     if x**2 + y**2 + z**2 + x*y + y*z + x*z > N:
#         break

for i in range(1, N+1):
    print(f[i].__len__())

### FIXED CODE ###

N = int(input().strip())

x, y, z = 1, 1, 1

f = [0] * (N + 1)

# while x**2 + y**2 + z**2 + x*y + y*z + x*z <= N:
def calc(x, y, z, f, axis="xyz"):
    # print(x, y, z)
    n = x**2 + y**2 + z**2 + x*y + y*z + x*z

    if n <= N:
        f[n] += 1
        if axis == "xyz":
            f = calc(x+1, y, z, f, axis="xyz")
            f = calc(x, y+1, z, f, axis="yz")
            f = calc(x, y, z+1, f, axis="z")
        elif axis == "yz":
            f = calc(x, y+1, z, f, axis="yz")
            f = calc(x, y, z+1, f, axis="z")
        elif axis == "z":
            f = calc(x, y, z + 1, f, axis="z")
        return f
    else:
        return f

f = calc(x, y, z, f)


for i in range(1, N+1):
    print(f[i])
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
ans = [0]*Q
for i in range(Q):
    l,r = map(int,input().split())
    ans[i]=S[l-1:r].count("AC")
for i in range(Q):
    print(ans[i])

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
t = [0]*(N+1)
l = [0]*Q
r = [0]*Q
for i in range(N-1):
	t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l,r = map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

N = int(input())
p = 1
for i in range(1, N+1):
    p *= i
print(p%(10**9+7))


### FIXED CODE ###

N = int(input())
p = 1
for i in range(1, N+1):
    p = (p*i)%(10**9+7)
print(p)