20250726

# def Q(k,n,m):
#     if m==n:
#         return(f(k-1,n))
#     else:
#         return(Q(k,n,m+1)+f(k-1,m))
# def f(k, n):
#     if me[k][n]==0:
#         me[k][n] = Q(k, n, 1)
#     return (me[k][n])
#
# me = []
# for x in range(16):
#     D=[]
#     for y in range(16):
#         D.append(0)
#     me.append(D)
# while True:
#     a, b=map(int, input().split())
#     for x in range(15):
#         me[0][x]=x
#     print(f(a, b))

# a, b=map(int, input().split())
# def f(r, c):
#     if m[r-1][c-1]==0:
#         m[r-1][c-1]=(f(r,c-1)+f(r-1,c))
#         m[c-1][r-1]=m[r-1][c-1]
#     return(m[r-1][c-1])
# m = []
# D = []
# K=[a,b]
# for y in range(max(K) + 1):
#     D.append(1)
# m.append(D)
# for x in range(max(K)):
#     D=[1]
#     for y in range(max(K)):
#         D.append(0)
#     m.append(D)
# print(f(a,b)%100000000)


# def f(n):
#     if n==0:
#         return(1)
#     return(f(n-1))*n
# a, b=map(int, input().split())
# if a<b:
#     print(0)
# else:
#     print((f(a)//f(b))//f(a-b))


n=int(input())
def f(n):