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

a = list(map(int,input().split()))
N = a[0]
K = a[1]

i = 2
x = (N-K+1)
y = 1
z = (x*y)%(10**9+7)
print(z)

while K >= i:
    if (N-K+1) >= i:
        x = (N-K+2-i)*x//i
        y = (K-i+1)*y//(i-1)
        z = (x*y)%(10**9+7)
        print(z)
        i = i + 1
    else:
        print(0)

### FIXED CODE ###

a = list(map(int,input().split()))
N = a[0]
K = a[1]

i = 2
x = (N-K+1)
y = 1
z = (x*y)%(10**9+7)
print(z)

while K >= i:
    if (N-K+1) >= i:
        x = (N-K+2-i)*x//i
        y = (K-i+1)*y//(i-1)
        z = (x*y)%(10**9+7)
        print(z)
    else:
        print(0)
    i = i + 1
### BUGGY CODE ###

numbers = input()

while numbers[1] == numbers[2]:
    if numbers.count(numbers[1], 0, 3) >= 3:
        print("Yes")
        exit()

print("No")

### FIXED CODE ###

numbers = input()

if numbers[1] == numbers[2]:
    if numbers.count(numbers[1]) >= 3:
        print("Yes")
        exit()

print("No")
### BUGGY CODE ###

N, M = map(int, input().split())
shop = [list(map(int, input().split())) for _ in range(N)]
drink = 0
money = 0

shop.sort(key=lambda x: x[0])

for i in range(N):
    for j in range(shop[i][1]):
        drink += 1
        money += shop[i][0]
        if drink == M:
            print(money)
            break




### FIXED CODE ###

from bisect import bisect_left
from itertools import accumulate

N, M = map(int, input().split())
shop = [list(map(int, input().split())) for _ in range(N)]
shop.sort(key=lambda x: x[0])

cnt = 0
ans = 0

for i in range(N):
    cnt += shop[i][1]
    if M <= cnt:
        dif = cnt - M
        ans += shop[i][0] * shop[i][1] - dif * shop[i][0]
        break
    else:
        ans += shop[i][0] * shop[i][1]

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

from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
L = 1
def lcm(x,y):
    return x//gcd(x,y)*y
for a in A:
    L = lcm(L,a)
ans=0
for a in A: ans+=L//a
print(ans%(10**9+7))

### FIXED CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
lcm = a[0]
for i in range(1,n):
  lcm = lcm*a[i] // gcd(lcm,a[i])
mod=pow(10,9)+7
lcm%=mod
ans=0
for x in a:
  ans+=pow(x,mod-2,mod)
  ans%=mod
print(ans*lcm%mod)
### BUGGY CODE ###

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

dp = [-1]*N
dp[0] = 0
dp[1] = abs(h[0] - h[1])

for i in range(2,N):
  dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(i-K,0),i))
print(dp[N-1])

### FIXED CODE ###

def main():
  N,K= map(int,input().split())
  h = list(map(int,input().split()))
  dp = [0]*N
  for i in range(1,N):
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(i-K,0),i))
  print(dp[N-1])

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

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [ 0 for i in range(N)]
for j in range(N):
    if j == 0:
        dp[j] = 0
    elif j == 1:
        dp[j] = abs(h[1]-h[0])
    elif j < K:
        check = []
        for a in range(j):
            check.append(dp[j-a-1]+abs(h[j]-h[j-a-1]))
        dp[j] = min(check)
    else:
        check = []
        for a in range(K):
            check.append(dp[j-a-1]+abs(h[j]-h[j-a-1]))
        dp[j] = min(check)
print(dp[N-1])

### FIXED CODE ###

#B
inf = float("inf")
N,K = map(int,input().split())
H = list(map(int,input().split()))

dp = [inf for _ in range(N)] #dp[i] = cost
dp[0] = 0
for i in range(N):
    for j in range(K):
        if i+j+1 < N:
            dp[i+j+1] = min(dp[i+j+1],dp[i]+abs(H[i]-H[i+j+1]))
            
#print(dp)
print(dp[N-1])
### BUGGY CODE ###

N, W = map(int, input().split())
items = [list(map(int, input().split())) for i in range(N)]

dpt = [0] * (W+1)

for w, v in items:
    for j in range(W, w-1, -1):
        dpt[j] = max(dpt[j], dpt[j-w] + v)

print(dpt[W])


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N, W = map(int, input().split())
    
    dpt = [0] * (W+1)
    
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(W, w-1, -1):
            a = dpt[j]
            b = dpt[j-w]+v
            if a > b:
                dpt[j] = a
            else:
                dpt[j] = b
    
    print(dpt[W])

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

N, K = map(int, input().split())
H = list(map(int, input().split()))
INF = 10 ** 9
dp = [INF] * N
dp[0] = 0

for i in range(N - 1):
  for k in range(1, K + 1):
    if i + k >= N: break
    dp[i + k] = min(dp[i + k], dp[i] + abs(H[i] - H[i + k]))

print(dp[-1])


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

def frog(n, k, h):
    d = [float('inf')] * n
    d[0] = 0

    for i in range(1, n):
        d[i] = min(
            d[j] + abs(h[i] - h[j]) for j in range(max(i - k, 0), i)
        )
    return d[n - 1]


print(frog(n, k, h))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
a = []
c = []
for i in range(M):
    a_,b=map(int,input().split())
    a.append(a_)
    c_tmp = list(map(int, input().split()))
    tmp=0
    for j in range(len(c_tmp)):
        tmp+=2**(c_tmp[j]-1)
    c.append(tmp)
INF = N*1e+6
dp = [INF]*2**N
dp[0]=0

for i in range(2**N):
    for j in range(M):
        dp[i|c[j]]=min(dp[i|c[j]], dp[i]+a[j])
if dp[2**N-1]==INF:
    print(-1)
    sys.exit()
print(dp[2**N-1])



### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
a = []
c = []
for i in range(M):
    a_,b=map(int,input().split())
    a.append(a_)
    c_tmp = list(map(int, input().split()))
    tmp=0
    for j in range(len(c_tmp)):
        tmp+=2**(c_tmp[j]-1)
    c.append(tmp)
INF = N*1e+6
dp = [INF]*2**N
dp[0]=0

for i in range(2**N):
    for j in range(M):
        dp[i|c[j]]=min(dp[i|c[j]], dp[i]+a[j])
if dp[2**N-1]==INF:
    print(-1)
    sys.exit()
print(dp[2**N-1])
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [1]
for i in range(n):
    b.append(a[i]*b[-1])
for i in range(n-k):
    if b[i+k+1]/b[i+1] > b[i+k]/b[i]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n-k):
    if a[i] < a[i+k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

l = input().split()
x = int(l[0])
k = int(l[1])
d = int(l[2])

for i in range(0, k):
  if abs(x + d) > abs(x - d):
    x -= d
  else:
    x += d
print(abs(x))

### FIXED CODE ###

X, K, D = map(int, input().split())
X = abs(X)

if X >= D * K:
  print(X - D * K)
else:
  K -= int(X / D)
  # for i in range(0, int(X/D)):
  #   X -= D
  X %= D
  if K % 2:
    print(D - X)
  else:
    print(X)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

MOD = 10**9+7

def dot(A, B):
    N = len(A)
    K = len(A[0])
    assert len(B) == K
    M = len(B[0])
    C = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            for k in range(K):
                C[i][j] += (A[i][k] * B[k][j]) % MOD
                C[i][j] % + MOD
    return C



def mp(A, n):
    assert len(A) == len(A[0])
    B = [[0] * len(A) for _ in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1

    while n:
        n, i = divmod(n, 2)
        if i:
            B = dot(A, B)
        A = dot(A, A)

    return B


ans = sum([sum(r) % MOD for r in mp(A, K)]) % MOD
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

MOD = 10**9+7

def dot(A, B):
    N = len(A)
    K = len(A[0])
    assert len(B) == K
    M = len(B[0])
    C = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            for k in range(K):
                C[i][j] += A[i][k] * B[k][j]
            C[i][j] %= MOD
    return C



def mp(A, n):
    assert len(A) == len(A[0])
    B = [[0] * len(A) for _ in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1

    while n:
        n, i = divmod(n, 2)
        if i:
            B = dot(A, B)
        A = dot(A, A)

    return B


ans = sum([sum(r) % MOD for r in mp(A, K)]) % MOD
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(map(int,input().split()))
t = []
r = []
m = []
o = 0
for i in range(n):
    if s[i] not in t:
        t.append(s[i])
        r.append(1)
        m.append(0)
    else:
        r[t.index(s[i])] += 1
    
    p = t.index(s[i])
    if r[p] - t[p] >= 0 and m[p] == 0:
        m[p] = 1
        r[p] -= t[p]

print(sum(r))

### FIXED CODE ###

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

for i,j in t.items():
    if i > j:
        o += j
    else:
        o += j - i

print(o)
### BUGGY CODE ###

H,W = map(int,input().split())
A=[]
x=[0]*(W+2)
A.append(x)
for i in range(H):
    a=list(map(int,input().split()))
    A.append([0]+a+[0])
A.append(x)
#print(A)

for i in range(H):
    b=list(map(int,input().split()))
    for j in range(W):
        A[i+1][j+1] = abs(A[i+1][j+1]-b[j])
        
#print(A)

L=[[set() for i in range(W+2)] for j in range(H+2)]
L[1][1].add(abs(A[1][1]))
#print(L)
#print(L[0][0])
for i in range(1,H+1):
    for j in range(1,W+1):
        #L[i][j]=list(L[i][j])
        for x in L[i][j]:
            if abs(x+A[i][j+1])<=6400:
                L[i][j+1].add(abs(x+A[i][j+1]))
            if abs(x-A[i][j+1])<=6400:
                L[i][j+1].add(abs(x-A[i][j+1]))
            if abs(x+A[i+1][j])<=6400:
                L[i+1][j].add(abs(x+A[i+1][j]))
            if abs(x-A[i+1][j])<=6400:
                L[i+1][j].add(abs(x-A[i+1][j]))
#print(L)

ans=10**5
L[H][W]=list(L[H][W])
for k in L[H][W]:
    if k<ans:
        ans=k
print(ans)


### FIXED CODE ###

H,W=map(int,input().split())
A=[]
A.append([0 for i in range(W+1)])
for i in range(H):
    a=[0]+list(map(int,input().split()))
    A.append(a)
B=[]
B.append([0 for i in range(W+1)])
for i in range(H):
    b=[0]+list(map(int,input().split()))
    B.append(b)
C=[[0 for i in range(W+1)]for j in range(H+1)]
for i in range(H+1):
    for j in range(W+1):
        C[i][j]=abs(A[i][j]-B[i][j])
        
ST=1<<80*160+1

dp=[[0 for i in range(W+1)]for j in range(H+1)]
dp[0][1]=ST
for i in range(1,H+1):
    for j in range(1,W+1):
        dp[i][j] |= (dp[i-1][j]<<C[i][j]) |(dp[i-1][j]>>C[i][j])
        dp[i][j] |= (dp[i][j-1]<<C[i][j]) |(dp[i][j-1]>>C[i][j])
#print(bin(dp[-1][-1]>>7))
ANS=list(bin(dp[-1][-1]>>80*160+1))[::-1]
#print(ANS)
for i in range(len(ANS)):
    if ANS[i]=="1":
        print(i)
        exit()
### BUGGY CODE ###

n = int(input())

f, a0 = map(int, input().split())

for i in range(n-1):
    t1, a1 = map(int, input().split())
    
    if f % t1 != 0:
        f += t1 - f % t1
    while (f // t1) * a1 < a0:
        f += t1
    a0 = (f // t1) * a1
print(f + a0)

### FIXED CODE ###

n = int(input())

t0, a0 = 1, 1

for i in range(n):
    t1, a1 = map(int, input().split())
    f0 = t0 // t1
    if t0 % t1 != 0:f0 += 1
    f1 = a0 // a1
    if a0 % a1 != 0:f1 += 1
    f = max(f0, f1)
    t0, a0 = t1*f, a1*f

print(t0 + a0)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
m=max(a)
for i in range(n):
  print(max([a[j] for j in range(n) if i!=j]))

### FIXED CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
m=max(a)
b=sorted(a)
for i in range(n):
  if a[i]==m:
    print(b[-2])
  else:
    print(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()
cnt = 0
for i, a in enumerate(A):
    X = make_divisors(a)
    for x in X:
        le = bisect.bisect_left(A, x, hi=i)
        re = bisect.bisect_right(A, x, hi=i)
        if le != re:
            cnt += 1
            break
        le = bisect.bisect_left(A, x, lo=i + 1)
        re = bisect.bisect_right(A, x, lo=i + 1)
        if le != re:
            cnt += 1
            break
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 ###

# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')


def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    d = defaultdict(int)
    for e in a:
        d[e] += 1
    sm = 0
    xd = defaultdict(int)
    for k in d:
        if d[k] >= 2:
            xd[k] = factorial(d[k]) // (2 * factorial(d[k]-2))
        sm += xd[k]
    for e in a:
        d[e] -= 1
        sm -= xd[e]
        x = 0
        if d[e] >= 2:
            x = factorial(d[e]) // (2 * factorial(d[e]-2))
        print(sm + x)
        sm += xd[e]
        d[e] += 1


    

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""


"""


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')


def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    d = defaultdict(int)
    for e in a:
        d[e] += 1
    sm = 0
    xd = defaultdict(int)
    for k in d:
        if d[k] >= 2:
            xd[k] = (d[k] * (d[k] - 1)) // 2
        sm += xd[k]
    for e in a:
        d[e] -= 1
        sm -= xd[e]
        x = 0
        if d[e] >= 2:
            x = (d[e] * (d[e] - 1)) // 2
        print(sm + x)
        sm += xd[e]
        d[e] += 1


    

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""


"""
### BUGGY CODE ###

A, B, K = map(int, input().split())

result = sorted(i for i in range(A, B + 1) if i - A + 1 <= K or B - i + 1 <= K)
for item in result:
    print(item)

### FIXED CODE ###

A, B, K = map(int, input().split())

if A + K - 1 >=  B - K + 1:
    for item in range(A, B + 1):
        print(item)
else:
    for item in range(A, A + K):
        print(item)
    for item in range(B - K + 1, B + 1):
        print(item)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split(" ")))
for j in range(n):
    s = 0
    x = 0
    for i in range(len(a)):
        if i == j:
            continue
        s += abs(a[i] - x)
        x = a[i]
    s += abs(0 - x)
    print(s)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(" ")))
s = 0
a.insert(0, 0)
a.insert(n+1, 0)
for j in range(n+1):
    s += abs(a[j] - a[j+1])
for i in range(1, n+1):
    s_i = s + abs(a[i-1]-a[i+1]) - ((abs(a[i-1] - a[i]) + abs(a[i]-a[i+1])))
    print(s_i)
### BUGGY CODE ###

from collections import*
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m=[input()for _ in range(h)]
d=[[I:=9**9]*w for _ in range(h)]
q=deque([(s-1,t-1,1)])
while q:
  y,x,c=q.popleft()
  if d[y][x]<I:continue
  d[y][x]=c
  for i,j in(y-1,x),(y,x-1),(y,x+1),(y+1,x):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]!='#':q.appendleft((i,j,c))
  for i,j in(y-2,x-2),(y-2,x-1),(y-2,x),(y-2,x+1),(y-2,x+2),(y-1,x-2),(y-1,x-1),(y-1,x+1),(y-1,x+2),(y,x-2),(y,x+2),(y+1,x-2),(y+1,x-1),(y+1,x+1),(y+1,x+2),(y+2,x-2),(y+2,x-1),(y+2,x),(y+2,x+1),(y+2,x+2):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]!='#':q.append((i,j,c+1))
print(d[f-1][g-1]%I-1)

### FIXED CODE ###

from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m=[input()for _ in range(h)]
d=[[I]*w for _ in range(h)]
q=deque([(s-1,t-1,1)])
while q:
  y,x,c=q.popleft()
  if d[y][x]<I:continue
  d[y][x]=c
  for i,j in(y-1,x),(y,x-1),(y,x+1),(y+1,x):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]!='#':q.appendleft((i,j,c))
  for i,j in(y-2,x-2),(y-2,x-1),(y-2,x),(y-2,x+1),(y-2,x+2),(y-1,x-2),(y-1,x-1),(y-1,x+1),(y-1,x+2),(y,x-2),(y,x+2),(y+1,x-2),(y+1,x-1),(y+1,x+1),(y+1,x+2),(y+2,x-2),(y+2,x-1),(y+2,x),(y+2,x+1),(y+2,x+2):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]!='#':q.append((i,j,c+1))
print(d[f-1][g-1]%I-1)
### BUGGY CODE ###

n,m = map(int,input().split())
x = [[int(i) for i in input().split()] for i in range(m)]

cnt = 0
for i in range(1,n+1):
    cnt_1 = 0
    for j in range(m):
        if i < x[j][0] or i > x[j][1]:
            cnt_1 = 1
            break

    if cnt_1 == 0:
        cnt += 1

print(cnt)

### FIXED CODE ###

n,m = map(int,input().split())
l = []
r = []
for i in range(m):
    l_x,r_x = map(int,input().split())
    l.append(l_x)
    r.append(r_x)

if min(r[0::])-max(l[0::])+1 >= 1:
    print(min(r[0::])-max(l[0::])+1)
else:
    print(0)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[i][j][3]
dp = [[[0] * 4 for _ in range(C + 5)] for _ in range(R + 5)]
for i in range(1, R + 3):
    for j in range(1, C + 3):
        # 行移動
        dp[i][j][0] = max(dp[i][j][0], max(dp[i - 1][j]))
        dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j]) + V[i][j])
        for k in range(4):
            # 列移動
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k - 1] + V[i][j])
            dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
print(max(dp[R][C]))


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[3][i][j]
dp = [[[0] * (C + 5) for _ in range(R + 5)] for _ in range(4)]
for i in range(R + 3):
    for j in range(C + 3):
        for k in range(4):
            # 行移動
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
            dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[k][i][j] + V[i + 1][j])
            # 列移動
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            if k < 3:
                dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], dp[k][i][j] + V[i][j + 1])
print(max(dp[k][R][C] for k in range(4)))
### BUGGY CODE ###

import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

def main():
    """"ここに今までのコード"""
    N, M = [int(x) for x in input().split()]
    S = [int(x) for x in input().split()]
    T = [int(x) for x in input().split()]

    DP = [[0] * (M + 1) for _ in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for n in range(1, N + 1):
        DP[n][0] = DP[n - 1][0]
        for m in range(1, M + 1):
            DP[n][m] = DP[n][m - 1] + DP[n - 1][m] - DP[n - 1][m - 1]
            if S[n - 1] == T[m - 1]:
                DP[n][m] += DP[n - 1][m - 1]
    print(DP[n][m] % MOD)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

def main():
    """"ここに今までのコード"""
    N, M = [int(x) for x in input().split()]
    S = [int(x) for x in input().split()]
    T = [int(x) for x in input().split()]

    DP = [[0] * (M + 1) for _ in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for n in range(1, N + 1):
        DP[n][0] = DP[n - 1][0]
        for m in range(1, M + 1):
            DP[n][m] = DP[n][m - 1] + DP[n - 1][m] - DP[n - 1][m - 1]
            DP[n][m] %= MOD
            if S[n - 1] == T[m - 1]:
                DP[n][m] += DP[n - 1][m - 1]
                DP[n][m] %= MOD
    print(DP[n][m])


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

from math import sqrt
N = int(input())
 
for n in range(1, N+1):
    count = 0
    for x in range(1, int(sqrt(n))):
        for y in range(1,int(sqrt(n))):
            for z in range(1, int(sqrt(n))):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    count += 1
    print(count)

### FIXED CODE ###

from math import sqrt
N = int(input())
ans = [0] * (N+1)

for x in range(1, int(sqrt(N)) + 2):
    for y in range(1,int(sqrt(N)) + 2):
        for z in range(1, int(sqrt(N)) + 2):
            n = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if n <= N:
                ans[n] += 1

for i in range(1, len(ans)):
    print(ans[i])
### BUGGY CODE ###

a, b, c = map(int, input().split())

i = 1
while a * i <= 10 ** 10:
    if (a * i) % b == c:
        print("YES")
        exit()
    i += 1

print("NO")

### FIXED CODE ###

a, b, c = map(int, input().split())

i = 1
while a * i <= b ** 2:
    if (a * i) % b == c:
        print("YES")
        exit()
    i += 1

print("NO")
### BUGGY CODE ###

def z_advanced(s, Z_max):
    """An advanced computation of Z-values of a string."""

    Z = [0] * len(s)
    Z[0] = len(s)

    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            # If k is outside the current Z-box, do naive computation.
            n = 0
            while n + k < len(s) and s[n] == s[n+k]:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k+n-1
        else:
            # If k is inside the current Z-box, consider two cases.

            p = k - lt  # Pair index.
            right_part_len = rt - k + 1

            if Z[p] < right_part_len:
                Z[k] = Z[p]
                    
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k

                lt = k
                rt = i - 1
                
        Z_max = max(Z_max, min(k, Z[k]))  # check_k_zk()を参考のこと
    
    # return Z, Z_max
    return Z_max
  
N = int(input())
S = input()
Z_max = 0
for i in range(N):
    Z_max = z_advanced(S[i:], Z_max)

print(Z_max)

### FIXED CODE ###

def z_advanced(s, Z_max):
    """An advanced computation of Z-values of a string."""

    Z = [0] * len(s)
    Z[0] = len(s)

    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            # If k is outside the current Z-box, do naive computation.
            n = 0
            while n + k < len(s) and s[n] == s[n+k]:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k+n-1
        else:
            # If k is inside the current Z-box, consider two cases.

            p = k - lt  # Pair index.
            right_part_len = rt - k + 1

            if Z[p] < right_part_len:
                Z[k] = Z[p]
                    
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k

                lt = k
                rt = i - 1
                
        Z_max = max(Z_max, min(k, Z[k]))  # check_k_zk()を参考のこと
    
    # return Z, Z_max
    return Z_max
  
N = int(input())
S = input()
Z_max = 0
for i in range(N):
    Z_max = z_advanced(S[i:], Z_max)

print(Z_max)