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

MAX = 10**9 + 7

def mod_inv(i, MOD):
    return pow(i, MOD-2, MOD)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up *= (_N - i) % MAX
        low *= (i + 1) % MAX
    ret = up * mod_inv(low, MAX)
    if ret >= MAX:
        ret %= MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = M*N* (M*(N+1)*(N-1) + N*(M+1)*(M-1)) / 6
    if disSum >= MAX:
        disSum %= MAX
    ret = disSum * combination(M*N-2, K-2)
    if ret >= MAX:
        ret %= MAX
    print ret

if __name__ == '__main__':
    solve()


### FIXED CODE ###

MAX = 10**9 + 7

def mod_inv(i, mod):
    return pow(i, mod-2, mod)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up = up * (_N - i) % MAX
        low = low * (i + 1) % MAX
    ret = up * mod_inv(low, MAX) % MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = (M*N* ((M*(N+1)*(N-1))%MAX + (N*(M+1)*(M-1)) % MAX)) % MAX
    disSum *= mod_inv(6, MAX) % MAX
    ret = disSum * combination(M*N-2, K-2) % MAX
    print ret

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

import sys
import Queue

n = int(raw_input())

graph = dict()
color = [-1 for i in range(0, n)]
for i in range(0, n - 1):
    u, v, w = map(int, raw_input().split(" "))
    graph[(u - 1, v - 1)] = w
    graph[(v - 1, u - 1)] = w

# for k, v in graph.items():
#     print("%s -> %d" % (str(k), v))

queue = Queue.Queue()
sum = 0
next_check = 0

while True:
    if sum >= n:
        break

    for i in range(next_check, n):
        if color[i] < 0:
            queue.put(i)
            color[i] = 0
            sum += 1
            next_check = i
            break

    while True:
        if queue.empty():
            break

        current_node = queue.get()
        for end in range(0, n):
            if (current_node, end) in graph and color[end] < 0:
                color[end] = (color[current_node] + graph[(current_node, end)] % 2) % 2
                queue.put(end)
                sum += 1

for node in range(0, n):
    print(color[node])


### FIXED CODE ###

import sys
import Queue

n = int(raw_input())

graph = dict()
color = [-1 for i in range(0, n)]
for i in range(0, n - 1):
    u, v, w = map(int, raw_input().split(" "))
    if (u - 1) in graph:
        graph[u - 1].append((v-1, w))
    else:
        graph[u - 1] = [(v-1, w)]

    if (v - 1) in graph:
        graph[v - 1].append((u - 1, w))
    else:
        graph[v - 1] = [(u - 1, w)]

# for start, value_list in graph.items():
#     for end, weight in value_list:
#         print("%s -> %d (%d)" % (start, end, weight))

queue = Queue.Queue()
sum = 0
next_check = 0

while True:
    if sum >= n:
        break

    for i in range(next_check, n):
        if color[i] < 0:
            queue.put(i)
            color[i] = 0
            sum += 1
            next_check = i
            break

    while True:
        if queue.empty():
            break

        current_node = queue.get()
        if current_node in graph:
            for end, weight in graph[current_node]:
                if color[end] < 0:
                    color[end] = (color[current_node] + weight % 2) % 2
                    queue.put(end)
                    sum += 1

for node in range(0, n):
    print(color[node])
### BUGGY CODE ###

s = input().strip()
N = len(s)
x,y = map(int,input().split())
AX = []
AY = []
flag = 0
cnt = 0
for i in range(len(s)):
    if s[i]=="F":
        cnt += 1
    else:
        if flag==0:
            AX.append(cnt)
            cnt = 0
            flag = 1
        else:
            AY.append(cnt)
            cnt = 0
            flag = 0
if cnt>0 and flag==0:
    AX.append(cnt)
if cnt>0 and flag==1:
    AY.append(cnt)
dpX = [[0 for _ in range(2*N+1)] for _ in range(len(AX)+1)]
if s[0]=="F":
    dpX[1][N+AX[0]] = 1
    for i in range(1,len(AX)):
        for j in range(2*N+1):
            if 0<=j+AX[i]<=2*N:
                dpX[i+1][j+AX[i]] = dpX[i+1][j+AX[i]] or dpX[i][j]
            if 0<=j-AX[i]<=2*N:
                dpX[i+1][j-AX[i]] = dpX[i+1][j-AX[i]] or dpX[i][j]
else:
    dpX[0][N] = 1
    for i in range(len(AX)):
        for j in range(2*N+1):
            if 0<=j+AX[i]<=2*N:
                dpX[i+1][j+AX[i]] = dpX[i+1][j+AX[i]] or dpX[i][j]
            if 0<=j-AX[i]<=2*N:
                dpX[i+1][j-AX[i]] = dpX[i+1][j-AX[i]] or dpX[i][j]
dpY = [[0 for _ in range(2*N+1)] for _ in range(len(AY)+1)]
dpY[0][N] = 1
for i in range(len(AY)):
    for j in range(2*N+1):
        if 0<=j+AY[i]<=2*N:
            dpY[i+1][j+AY[i]] = dpY[i+1][j+AY[i]] or dpY[i][j]
        if 0<=j-AY[i]<=2*N:
            dpY[i+1][j-AY[i]] = dpY[i+1][j-AY[i]] or dpY[i][j]
if dpX[len(AX)][N+x]==1 and dpY[len(AY)][N+y]==1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input().strip()
x,y = map(int,input().split())
C = {}
cur = 0
cnt = 0
for i in range(len(s)):
    if s[i]=="F":
        cnt += 1
    else:
        C[cur] = cnt
        cur += 1
        cnt = 0
C[cur] = cnt
AX = []
AY = []
for a in C:
    if a>0 and a%2==0 and C[a]>0:
        AX.append(C[a])
    elif a%2==1 and C[a]>0:
        AY.append(C[a])
cntx = sum(AX)
dpx = [[0 for _ in range(2*cntx+1)] for _ in range(len(AX)+1)]
dpx[0][cntx] = 1
if cntx>0:
    dpx[1][cntx-AX[0]] = 1
    dpx[1][cntx+AX[0]] = 1
    for i in range(2,len(AX)+1):
        for j in range(-cntx,cntx+1):
            if -cntx<=j-AX[i-1]:
                dpx[i][j+cntx] = dpx[i-1][j-AX[i-1]+cntx]
                if j+AX[i-1]<=cntx:
                    dpx[i][j+cntx] = max(dpx[i][j+cntx],dpx[i-1][j+AX[i-1]+cntx])
            elif j+AX[i-1]<=cntx:
                dpx[i][j+cntx] = dpx[i-1][j+AX[i-1]+cntx]
cnty = sum(AY)
dpy = [[0 for _ in range(2*cnty+1)] for _ in range(len(AY)+1)]
dpy[0][cnty] = 1
if cnty>0:
    dpy[1][cnty-AY[0]] = 1
    dpy[1][cnty+AY[0]] = 1
    for i in range(2,len(AY)+1):
        for j in range(-cnty,cnty+1):
            if -cnty<=j-AY[i-1]:
                dpy[i][j+cnty] = dpy[i-1][j-AY[i-1]+cnty]
                if j+AY[i-1]<=cnty:
                    dpy[i][j+cnty] = max(dpy[i][j+cnty],dpy[i-1][j+AY[i-1]+cnty])
            elif j+AY[i-1]<=cnty:
                dpy[i][j+cnty] = dpy[i-1][j+AY[i-1]+cnty]
if C[0]-cntx<=x<=C[0]+cntx and dpx[len(AX)][x-C[0]+cntx]==1 and -cnty<=y<=cnty and dpy[len(AY)][y+cnty]==1:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

class SegmentTree:
    def __init__(self, n, op, e):
        self.n = 1 << (n - 1).bit_length()
        self.op = op
        self.e = e
        self.data = [e] * (2 * self.n)

    def update(self, k, v):
        k += self.n
        self.data[k] = v
        while k > 0:
            k >>= 1
            self.data[k] = self.op(self.data[2 * k], self.data[2 * k + 1])

    def query(self, left, right):
        left += self.n
        right += self.n
        l_res = self.e
        r_res = self.e
        while left < right:
            if left & 1:
                l_res = self.op(l_res, self.data[left])
                left += 1
            left >>= 1
            if right & 1:
                right -= 1
                r_res = self.op(self.data[right], r_res)
            right >>= 1
        return self.op(l_res, r_res)


MOD = 998244353
N, K, *LR = map(int, open(0).read().split())
segments = [(l, r) for l, r in zip(*[iter(LR)] * 2)]
st = SegmentTree(N + 1, lambda x, y: (x + y) % MOD, 0)
st.update(0, 1)
for i in range(1, N + 1):
    for l, r in segments:
        if i - l < 0:
            continue
        L = max(i - r, 0)
        R = i - l
        st.update(i, st.query(i, i + 1) + st.query(L, R + 1))
print(st.query(N - 1, N))


### FIXED CODE ###

class SegmentTree:
    def __init__(self, n, op, e):
        self.n = 1 << (n - 1).bit_length()
        self.op = op
        self.e = e
        self.data = [e] * (2 * self.n)

    def update(self, k, v):
        k += self.n
        self.data[k] = v
        while k > 0:
            k >>= 1
            self.data[k] = self.op(self.data[2 * k], self.data[2 * k + 1])

    def query(self, left, right):
        left += self.n
        right += self.n
        l_res = self.e
        r_res = self.e
        while left < right:
            if left & 1:
                l_res = self.op(l_res, self.data[left])
                left += 1
            left >>= 1
            if right & 1:
                right -= 1
                r_res = self.op(self.data[right], r_res)
            right >>= 1
        return self.op(l_res, r_res)


MOD = 998244353
N, K, *LR = map(int, open(0).read().split())
segments = [(l, r) for l, r in zip(*[iter(LR)] * 2)]
st = SegmentTree(N + 1, lambda x, y: (x + y) % MOD, 0)
st.update(0, 1)
for i in range(1, N + 1):
    for l, r in segments:
        if i - l < 0:
            continue
        L = max(i - r, 0)
        R = i - l
        st.update(i, st.query(i, i + 1) + st.query(L, R + 1))
print(st.query(N - 1, N))
### BUGGY CODE ###

n=int(input())
p=list(map(int, input().split()))
c=0
for k in range(1, max(p)+1):
  arc = []
  abc = []
  for i in p:
    if k >= i:
      arc.append(arc)
    elif k <= i:
      abc.append(abc)
  if len(arc) == len(abc):
    c+=1
print(c)
  
      
  

### FIXED CODE ###

n=int(input())
p=sorted(list(map(int, input().split())))
print(p[int(n/2)]-p[int(n/2)-1])
### BUGGY CODE ###

Q = int(raw_input())
L, R = [], []
for i in range(Q):
	l_r = [int(num) for num in raw_input().split()]
	L.append(l_r[0])
	R.append(l_r[1])

max_num = max(R)
def decide_sosu(max_num):
	sosus_nokori = range(2, max_num + 1)
	sosus = []
	while len(sosus_nokori) > 0:
		min_i = min(sosus_nokori)
		sosus.append(min_i)
		sosus_nokori.remove(min_i)
		for num in range(min_i*min_i, max_num+1, min_i):
			if num in sosus_nokori:
				sosus_nokori.remove(num)
	return sosus

sosus = decide_sosu(max_num+1)

c_s = [0] * (max_num + 1)
for i in range(2, max_num + 1):
	if (i in sosus) & (((i+1) % 2)==0) & ((i+1)/2 in sosus): 
		c_s[i] = c_s[i-1] + 1
	else:
		c_s[i] = c_s[i-1]

for i in range(Q):
	print c_s[R[i]] - c_s[L[i]-1]

### FIXED CODE ###

import math
Q = int(raw_input())
L, R = [], []
for i in range(Q):
	l_r = [int(num) for num in raw_input().split()]
	L.append(l_r[0])
	R.append(l_r[1])

max_num = max(R)
def calc_sosus(max_num):
	IsPrimes = [True] * (max_num + 1)
	IsPrimes[0] = False
	IsPrimes[1] = False
	for min_i in range(2, int(math.sqrt(max_num)) + 1):
		if IsPrimes[min_i]:
			for num in range(min_i*min_i, max_num+1, min_i):
				IsPrimes[num] = False
	return IsPrimes

IsPrimes = calc_sosus(max_num)

c_s = [0] * (max_num + 1)
for i in range(2, max_num + 1):
	if (IsPrimes[i]) & (((i+1) % 2)==0) & (IsPrimes[(i+1)/2]): 
		c_s[i] = c_s[i-1] + 1
	else:
		c_s[i] = c_s[i-1]

for i in range(Q):
	print c_s[R[i]] - c_s[L[i]-1]
### BUGGY CODE ###

s = input()

mod = [1] + [0]*2018
t = 0
a = 0
n = len(s)
s = s[::-1]
for i in range(n):
    t += int(s[i]) * (10 ** a)
    a += 1
    mod[t%2019] += 1
    #print(t,t%2019)
ans = 0
for i in range(2019):
    ans += mod[i]*(mod[i]-1)//2
print(ans)

### FIXED CODE ###

s = input()
#s = '9' * 200000

mod = [1] + [0]*2018
t = 0
a = 1
n = len(s)
s = s[::-1]
for i in range(n):
    t = (t + int(s[i])*a) % 2019
    a = a * 10 % 2019
    mod[t] += 1
ans = 0
for i in range(2019):
    ans += mod[i]*(mod[i]-1)//2
print(ans)
### BUGGY CODE ###

import sys


def popcount(n):
    return '{:b}'.format(n).count('1')


def f(n, firstpopcount):
    if not n:
        return 0
    i = 1
    n %= firstpopcount
    # print(f'{n=}')
    while n:
        i += 1
        n %= popcount(n)
    return i


def resolve(in_):
    n = int(in_.readline())
    x = int(in_.readline(), 2)
    xpopcount = popcount(x)
    for i in range(n - 1, -1, -1):
        s = 2 ** i
        v = x ^ s

        if v & s:
            firstpopcount = xpopcount + 1
        else:
            firstpopcount = xpopcount - 1

        # print(f'{x=:b} {v=:b} {1<<i=:b}')
        print(f(v, firstpopcount))


def main():
    resolve(sys.stdin.buffer)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys


def popcount(n):
    c = 0
    while n:
        if n & 1:
            c += 1
        n >>= 1

    return c


def f(n, c=0):
    while pc := popcount(n):
        n %= pc
        c += 1

    return c


def _resolve(n, x_bytes):
    one_i = b'1'[0]
    pc_x = x_bytes.count(b'1')

    i2_mod_pc_x_p1 = [0] * n
    i2_mod_pc_x_m1 = [0] * n
    x_mod_pc_x_p1 = 0
    x_mod_pc_x_m1 = 0

    i2 = 1
    x = 0
    mod = pc_x + 1
    for a in range(n):
        i2_mod_pc_x_p1[- 1 - a] = i2
        i2 *= 2
        i2 %= mod

        x *= 2
        x %= mod
        if (x_bytes[a] == one_i):
            x += 1
    x_mod_pc_x_p1 = x % mod

    if pc_x > 1:
        i2 = 1
        x = 0
        mod = pc_x - 1
        for a in range(n):
            i2_mod_pc_x_m1[- 1 - a] = i2
            i2 *= 2
            i2 %= mod

            x *= 2
            x %= mod
            if (x_bytes[a] == one_i):
                x += 1
        x_mod_pc_x_m1 = x % mod

    # print(pc_x)
    # print(x_mod_pc_x_p1)
    # print(x_mod_pc_x_m1)

    # print(i2_mod_pc_x_p1)
    # print(i2_mod_pc_x_m1)

    for a in range(n):
        if x_bytes[a] == one_i:
            mod = pc_x - 1
            if mod == 0:
                yield 0
                continue
            b = x_mod_pc_x_m1 - i2_mod_pc_x_m1[a]
        else:
            mod = pc_x + 1
            b = x_mod_pc_x_p1 + i2_mod_pc_x_p1[a]
        b %= mod

        yield f(b, 1)

def resolve(in_, out):
    n = int(in_.readline())
    x_bytes = in_.readline()
    for ret in _resolve(n, x_bytes):
        print(ret, file=out)


def main():
    resolve(sys.stdin.buffer, sys.stdout)


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

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

def CalExVal(x):
    return (1/2*(x+1))
Ex = list(map(CalExVal, A))
adjlist = [0]*(len(A)-K+1)

for i in range(len(A)-K + 1):
    adjlist[i] = sum(Ex[i:(K+i)])

print(max(adjlist))

### FIXED CODE ###

def main():
  def CalExVal(x):
    return (1/2*(x+1))
  N, K = map(int, input().split())
  A = list(map(int, input().split()))


  Ex = list((map(CalExVal, A)))
  #temp = len(A)-K + 1
  #adjlist = [0]*(temp)
  #adjlist = [sum(list(map(CalExVal, A))[i:(K+i)]) for i in range(temp)]
  tem = sum(Ex[:K])
  res = tem
  for i in range(0,N-K):
      tem = tem - Ex[i] + Ex[i+K]
      if res < tem:
      	res = tem
  print(res)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

h, w, d = input().split()
h = int(h)
w = int(w)
d = int(d)

a = []
for i in range(h):
    b = list(map(int, input().split()))
    a.append(b)

q = int(input())
l = []
r = []
for j in range(q):
    L, R = list(map(int, input().split()))
    l.append(L)
    r.append(R)

magic = 0

def search(word):
    for i in range(w):
        for j in range(h):
            if a[j][i] == word:
                return j+1, i+1




for k in range(q):
    x = 0
    y = 0
    magic = 0
    while True:
        if l[k] == r[k]:
            break
        else:
            if x != 0:
                i, j = x, y
            else:
                i, j = search(l[k])
            l[k] += d
            x, y = search(l[k])

            magic += abs(x-i)+abs(y-j)
    print(magic)

### FIXED CODE ###

h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]

memo = [[] for i in range(h*w)]
for i in range(h):
    for j in range(w):
        memo[a[i][j]-1].append((i, j))

cost = [0 for i in range(h*w)]
for t in range(d, h*w):
    i, j = memo[t-d][0]
    x, y = memo[t][0]
    cost[t] = abs(x-i) + abs(y-j)
for s in range(d):
    for i in range(s, h*w-d, d):
        cost[i+d] += cost[i]

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(cost[r-1]-cost[l-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        x,y=map(int,input().split())
        x-=1; y-=1
        E[x].append(y)
        E[y].append(x)
    dp=[[-1]*2 for _ in range(n)] # dp[i][color] 白:0 黒:1
    def dfs(v,p)->NoneType:
        if(dp[v][0]!=-1 and dp[v][1]!=-1): return
        white=black=1
        for nv in E[v]:
            if(nv==p): continue
            dfs(nv,v)
            white*=dp[nv][0]+dp[nv][1] # 白は常にOK
            white%=MOD
            black*=dp[nv][0]           # 黒は子の全てが白のときのみ
            black%=MOD
        dp[v][0]=white
        dp[v][1]=black
    dfs(0,-1)
    print((dp[0][0]+dp[0][1])%MOD)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)
    deg = [len(E[v]) - 1 for v in range(n)]
    deg[0] += 1

    topological_sort = []
    parent = [None] * n
    stack = [(~0, -1), (0, -1)] # (v, p)
    while stack:
        v, p = stack.pop()
        if v >= 0:
            parent[v] = p
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            if deg[~v] == 0:
                topological_sort.append(~v)
            deg[p] -= 1

    dp = [[None] * 2 for _ in range(n)]
    for v in topological_sort:
        white = black = 1
        for nv in E[v]:
            if nv == parent[v]:
                continue
            white *= dp[nv][0] + dp[nv][1]
            black *= dp[nv][0]
            white %= MOD
            black %= MOD
        dp[v][0] = white
        dp[v][1] = black

    print((dp[0][0] + dp[0][1]) % MOD)
resolve()
### BUGGY CODE ###

n = int(input())
ans = 1
limit = 10**18
for x in input().split():
    x = int(x)
    ans *= x
    if(x==0):
        print(x)
        exit()


if(ans > limit):
        print(-1)
        exit()    
print(ans)


### FIXED CODE ###

n = int(input())
ans = 1
l = [int(x) for x in input().split()]
limit = 10**18
if(0 in l):
    print(0)
    exit()

for x in l:
    x = int(x)
    ans *= x

    if(ans > limit):
        print(-1)
        exit()    

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

import sys
from heapq import heappush, heappop, heapify
n = int(input())
a = [int(e) for e in input().split()]
b = [int(e) for e in input().split()]
result = 0
finished = 0
hq = [(-b[i], i) for i in range(n)]
heapify(hq)
while True:
  _, i = heappop(hq)
  if a[i] == b[i]:
    finished += 1
    continue
  if i == 0:
    b[i] -= b[n - 1] + b[1]
  elif i == n -1:
    b[i] -= b[n - 2] + b[0]
  else:
    b[i] -= b[i - 1] + b[i + 1]
  if a[i] > b[i]:
    print(-1)
    sys.exit()
  result += 1
  if a[i] == b[i]:
    finished += 1
    if finished == n:
      print(result)
      sys.exit()
  else:
    heappush(hq, (-b[i], i))


### FIXED CODE ###

def main():
  import sys
  _int = int
  n = _int(input())
  a = [_int(e) for e in input().split()]
  b = [_int(e) for e in input().split()]
  result = 0
  q = [i for i in range(n) if b[i] != a[i]]
  while len(q) != 0:
    nq = []
    c = 0
    for i in q:
      if i == 0 or i == n - 1:
        j = b[(n + i - 1) % n] + b[(n + i + 1) % n]
      else:
        j = b[i - 1] + b[i + 1]
      if j > b[i] - a[i]:
        nq.append(i)
        continue
      c += 1
      k = (b[i] - a[i]) // j
      result += k
      b[i] -= j * k
      if a[i] != b[i]:
        nq.append(i)
    if c == 0 and len(nq) != 0:
      print(-1)
      sys.exit()
    q = nq
  print(result)
main()
### BUGGY CODE ###

s = list(map(int, input().split()))
n=s[0]
w=s[1]
dp=[[0]*(w+1) for i in range(n+1)]
weight=[]
value=[]
for i in range(n):
    s = list(map(int, input().split()))
    weight.append(s[0])
    value.append(s[1])

for i in range(n):
    for j in range(w+1):
        if weight[i]<=w and weight[i]<=j:
            dp[i+1][j]=max(dp[i][j-weight[i]]+value[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[n][w])

### FIXED CODE ###

import numpy as np

n,W=list(map(int,input().split()))

dp=np.zeros([n+1,W+1],dtype=int)

for i in range(1,n+1):
    w,v=list(map(int,input().split()))
    dp[i]=dp[i-1]
    dp[i][w:]=np.maximum(dp[i-1][:W-w+1]+v,dp[i-1][w:])
print(np.max(dp))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(6500)

def find(n):
    if d[n]<0:
        return n
    else:
        d[n]=find(d[n])
        return d[n]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def members(n):
    p=find(n)
    ans=[]
    for i in range(N):
        if find(i)==p:
            ans.append(i)
    return ans

N,M=map(int,input().split())
p=list(map(int,input().split()))

d=[-1]*N

for i in range(M):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    union(x,y)

ans=0
for i in range(N):
    lis=members(i)
    for j in lis:
        if i+1==p[j]:
            ans+=1
            break
print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(6500)

def find(n):
    if d[n]<0:
        return n
    else:
        d[n]=find(d[n])
        return d[n]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def members(n):
    p=find(n)
    ans=[]
    for i in range(N):
        if find(i)==p:
            ans.append(i)
    return ans

def same(a,b):
    if find(a)==find(b):return True
    else:return False

N,M=map(int,input().split())
p=list(map(int,input().split()))

d=[-1]*N

for i in range(M):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    union(x,y)

ans=0
for i in range(N):
    if same(i,p[i]-1):
        ans+=1
print(ans)
### BUGGY CODE ###

n, x, y = map(int, input().split(' '))
d_list = []
for i in range(1, n):
    for j in range(i + 1, n + 1):
        if j <= x or y <= i:  # ok
            d_list.append(j - i)
        elif i <= x and x < j <= y:
            d_list.append(min(j - i, x - i + y - j + 1))
        elif i <= x and j > y: # ここまでok
            d_list.append(x - i + j - y + 1)
        elif x < i < y and j < y:
            d_list.append(min(j - i, i - x + y - j + 1))
        elif x < i < y and j >= y:
            d_list.append(min(j - i, i - x + j - y + 1))
for i in range(1, n):
    print(d_list.count(i))

### FIXED CODE ###

n, x, y = map(int, input().split(' '))
d_dict = {i:0 for i in range(1, n)}
for i in range(1, n):
    for j in range(i + 1, n + 1):
        if j <= x or y <= i:
            d_dict[j - i] += 1
        elif i <= x and x < j <= y:
            d_dict[min(j - i, x - i + y - j + 1)] += 1
        elif i <= x and j > y:
            d_dict[x - i + j - y + 1] += 1
        elif x < i < y and j < y:
            d_dict[min(j - i, i - x + y - j + 1)] += 1
        elif x < i < y and j >= y:
            d_dict[min(j - i, i - x + j - y + 1)] += 1
for i in range(1, n):
    print(d_dict[i])
### BUGGY CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0
    q_prev = A
    q_next = []

    while len(q_prev) > 1:
        a = q_prev[0]
        if a != q_prev[1]:
            ans += 1

        for ai in q_prev:
            if ai % a != 0:
                q_next.append(ai)

        q_prev, q_next = q_next, []

    print(ans + len(q_prev))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    D = [True] * (10**6 + 1)
    ans = 0

    for i, a in enumerate(A):
        if not D[a]:
            continue
        if (i < n-1 and a != A[i+1]) or i == n-1:
            ans += 1

        j = a
        while (j < 10**6 + 1):
            D[j] = False
            j += a

    print(ans)


if __name__ == '__main__':
    main()