Harryxun/stf_run huggingface dataset:
import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
#import heapq
import math
start=time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = rl()
a=rl()
a.sort()
b=[0]*2*10**5
ans=[]
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
for i in a:
    f=True
    if b[i]==1:
        if ans:
            if i in ans:
                ans.remove(i)
        continue
    for j in make_divisors(i):
        if b[j]==1:
            f=False
            break
    if f:
        b[i]=1
        ans.append(i)

print(len(ans))

### FIXED CODE ###

import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
#import heapq
import math
start=time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = rl()
a=rl()
a.sort()
b=[0]*2*10**6
for i in a:
    if b[i]==0:
        b[i]=-1
        for j in range(2,10**6):
            if i*j>10**6:
                break
            b[i*j]+=1
        continue
    
    if b[i]==-1:
        b[i]=1
cnt = 0
for i in a:
    if b[i]==-1:
        cnt+=1
print(cnt)
from collections import Counter
from functools import lru_cache

@lru_cache(maxsize=None)
def dp(N, c1, c2, c3):
    if c1 + c2 + c3 == 0:
        return 0
    r = N
    if c1:
        r += c1 * dp(N, c1 - 1, c2, c3)
    if c2:
        r += c2 * dp(N, c1 + 1, c2 - 1, c3)
    if c3:
        r += c3 * dp(N, c1, c2 + 1, c3 - 1)
    return r / (c1 + c2 + c3)

def main():
    N = int(input())
    a = list(map(int, input().split()))
    a = Counter(a)
    print(dp(N, a.get(1, 0), a.get(2, 0), a.get(3, 0)))


main()


### FIXED CODE ###

from collections import Counter

def main():
    N = int(input())
    a = Counter(map(int, input().split()))
    a1, a2, a3 = a.get(1, 0), a.get(2, 0), a.get(3, 0)
    a123 = a1 + a2 + a3 + 1
    u = [[0.0] * (a123 - c2) for c2 in range(a123)]
    v = [[0.0] * (a123 - c2) for c2 in range(a123)]
    t1 = 0.0
    v2 = v[0]
    for c1 in range(1, a123):
        v2[c1] = t1 = N / c1 + t1
    for c2 in range(1, a123):
        v2 = v[c2]
        for c1, t2 in zip(range(301 - c2), v[c2 - 1][1:]):
            v2[c1] = t1 = (N + c1 * t1 + c2 * t2) / (c1 + c2)

    for c3 in range(1, a3 + 1):
        u, v = v, u
        v2 = v[0]
        for c1, t3 in zip(range(a123 - c3), u[1]):
            v2[c1] = t1 = (N + c1 * t1 + c3 * t3) / (c1 + c3)
        for c2 in range(1, a123 - c3):
            v2 = v[c2]
            c23 = c2 + c3
            for c1, t2, t3 in zip(range(a123 - c3 - c2), v[c2 - 1][1:], u[c2 + 1]):
                v2[c1] = t1 = (N + c1 * t1 + c2 * t2 + c3 * t3) / (c1 + c23)

    print(v[a2][a1])
main()
n = int(input())
x = list(map(str, input().split()))
sx = sorted(x)

max_mid = sx[int(n/2)+1]
min_mid = sx[int(n/2)]

for i in x:
    if i <= min_mid:    # 左半分から取られてる時
        print(max_mid)
    else:               # 右半分から取られてる時
        print(min_mid)


### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
sx = sorted(x)

min_mid = sx[int(n/2-1)]
max_mid = sx[int(n/2)]

for i in x:
    if i <= min_mid:    # 左半分から取られてる時
        print(max_mid)
    else:               # 右半分から取られてる時
        print(min_mid)
import math
N, X, T = map(int, input().split())
print(math.ceil(n / x) * t)


### FIXED CODE ###

n, x, t = map(int, input().split())
if n % x == 0:
  print((n//x)*t)
else:
  print(((n//x)+1)*t)
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n = i_input()
    a = i_list()

    k = [0]
    for i in range(2*10):
        k.append(k[i]+(i+1))
    t = a.copy()
    t.sort()

    s = 0

    m = [0]*n

    for i,n in itertools.groupby(t):
        l = len(list(n))
        s += k[l-1]
        if l > 1:
            m[i-1] = k[l-2] - k[l-1]

    for i in a:
        print(s + m[i-1])







if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n = i_input()
    a = i_list()

    k = [0]
    for i in range(2*10**5):
        k.append(k[i]+(i+1))
    t = a.copy()
    t.sort()

    s = 0

    m = [0]*n

    for i,n in itertools.groupby(t):
        l = len(list(n))
        s += k[l-1]
        if l > 1:
            m[i-1] = k[l-2] - k[l-1]

    for i in a:
        print(s + m[i-1])







if __name__=="__main__":
    main()
import numpy as np

n, m = map(int, input().split())
aa = [int(ak) % m for ak in input().split()]
mod = np.zeros(m,dtype="i4")
ans = 0
for a in aa:
    mod=np.roll(mod,a)
    mod[a] += 1
    ans += mod[0]
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
aa = [int(ak) % m for ak in input().split()]
mod = {}
ans = 0
zi = 0
for a in aa:
    zi = (zi - a) % m
    ai = (zi + a) % m
    mod.setdefault(ai,0)
    mod[ai] += 1
    ans += mod.get(zi,0)
print(ans)
K = 32
P = 998244353
m = int(("1" * 2 + "0" * 30) * (S + 1), 2)
mm = (1 << K * (S + 1)) - 1
pa = (1 << 30) - ((1 << 30) % P)

M = []
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s -= ((s & m) >> 30) * pa
    ans += s >> S * K

print(ans % P)

### FIXED CODE ###

N, S = map(int, input().split())
A = [int(a) for a in input().split()]
X = [0] * 3001
pre = 0
ans = 0
P = 998244353
for i, a in enumerate(A):
    for j in range(S, a, -1):
        X[j] = (X[j] + X[j-a]) % P
    X[a] = (X[a] + i + 1) % P
    ans = (ans + (X[S] - pre) * (N - i)) % P
    pre = X[S]
print(ans)
N, A, B, C = map(int, input().split())
SN = [input() for _ in range(N)]

ABC = {'A': A, 'B': B, 'C': C}
ans = [""] * N
# print('ABC : ' + str(ABC))

# Recursiveにすることによって、途中で負の値になってもいくらでも遡ることが可能となる
def recursive_exec(i):
  # 最後まで辿り着いたらクリア
  if i == N:
    print('Yes')
    print("\n".join(ans))
    quit()
  for L, R in (SN[i], reversed(SN[i])):	# ex) L, R in ('AB', 'BA')
    if ABC[L] > 0: # LでもRでもどちらでも良い
      ABC[L] -= 1
      ABC[R] += 1
      ans[i] = L

      # Next
      recursive_exec(i+1)

      # 0以下になったら戻して別の文字でやってみる (reversed(SN[i]))
      ABC[L] += 1
      ABC[R] -= 1

recursive_exec(0)
print('No')

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

*I, = open(0).read().split()
N, A, B, C = map(int, I[:4])
S = I[4:]

Cnt = {"A": A, "B": B, "C": C}

ans = [""] * N
def dfs(i):
    if i == N:
        print("Yes")
        print("\n".join(ans))
        quit()

    for L, R in (S[i], reversed(S[i])):
        if Cnt[R] > 0:
            Cnt[L] += 1
            Cnt[R] -= 1

            ans[i] = L
            dfs(i + 1)

            Cnt[L] -= 1
            Cnt[R] += 1


dfs(0)
print("No")
N = int(input())
A = list(map(int, input().split()))
 
ans = 1
 
for i in N:
  ans *= A[i]
  
  if ans > 10 ** 18:
  print(-1)
  return 
  

  
print(ans)

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
 
    if 0 in A:
        print(0)
        return
    
    ans = 1
 
    for i in A:
        ans *= i
      
        if ans > 10 ** 18:
            print(-1)
            return 
      
    print(ans)  

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

before_A = A/0.08
before_B = B/0.1

if A > B:
    print(-1)
    break
else:
    if before_A <= before_B:
        ans = before_B
        if int(before_B * 0.08) == A:
            print(int(ans))
        else:
            print(-1)
    else:
        ans = before_A
        if int(before_A * 0.1) == B:
            print(int(ans))
        else:
            print(-1)

### FIXED CODE ###

a,b=map(int,input().split())
for i in  range(1,1300):
  if int(i*0.08)==a and int(i*0.1)==b:
    print(i)
    exit()
print(-1)
import math
N=int(input())
engines = tuple((complex(*map(int, input().split())) for _ in range(N)))
engines = sorted(list((engine, math.atan2(engine.imag, engine.real))for engine in engines if engine != 0), key=lambda x:x[1])
N = len(engines)
total = sum(engine[0] for engine in engines)
head_index = max(i if engines[i][0].imag < 0 else -1 for i in range(N))
tail_index = 0
tmp = sum(engines[i][0] for i in range(tail_index,head_index+1))
maximum = max(abs(tmp), abs(total - tmp))

while True:
    if head_index < N-1:
        if (engines[head_index+1][0]/engines[tail_index][0]).imag >= 0:
            head_index += 1
        else:
            tail_index += 1
    else:
        if (engines[0][0]/engines[tail_index][0]).imag < 0:
            tail_index += 1
        else:
            break
    tmp = sum(engines[i][0] for i in range(tail_index,head_index+1))
    maximum = max(maximum, abs(tmp), abs(total - tmp))

print(maximum)

### FIXED CODE ###

import math
N=int(input())
engines = tuple((complex(*map(int, input().split())) for _ in range(N)))
engines = sorted(list((engine, math.atan2(engine.imag, engine.real))for engine in engines if engine != 0), key=lambda x:x[1])
N=len(engines)
if N == 0:
    print(0)
else:
    total = sum(engine[0] for engine in engines)
    head_index = max(i if engines[i][0].imag < 0 else -1 for i in range(N))
    tail_index = 0
    tmp = sum(engines[i][0] for i in range(tail_index,head_index+1))
    maximum = max(abs(tmp), abs(total - tmp))

    while True:
        if head_index < N-1:
            if (engines[head_index+1][0]/engines[tail_index][0]).imag >= 0:
                head_index += 1
            else:
                tail_index += 1
        else:
            if (engines[0][0]/engines[tail_index][0]).imag < 0:
                tail_index += 1
            else:
                break
        tmp = sum(engines[i][0] for i in range(tail_index,head_index+1))
        maximum = max(maximum, abs(tmp), abs(total - tmp))

    print(maximum)
n,*L = map(int,open(0).read().split())
sum1 = sum(L)
L.sort()
if sum1%10 != 0:
    print(sum1)
    exit()
i = 0
while sum1%10==0:
    sum1 -= L[i]
    if sum1 < 0:
        sum1 = 0
    i +=1
print(sum1)

### FIXED CODE ###

n = int(input())
li = []
for i in range(n):
    li.append(int(input()))
li.sort()
flag1 = False
flag2 = False
flag3 = False
if sum(li)%10 != 0:
    flag2 = True

for i in range(n):
    if (sum(li) - li[i])%10 != 0 and flag2 == False:
        flag1 = True
        break
    else:
        flag3 =True
    
if flag1:
    print (sum(li) - li[i])
elif flag2:   
    print(sum(li))
elif flag3:
    print(0)
def solve() :
    a, b = input().split()

    a = int(a)
    b = b.replace('.', '')
    b100 = int(b[0])*100 + int(b[1])*10 + int(b[2])*1

    print(a*b100//100)
    return


if __name__ == "__main__" :
    solve()

### FIXED CODE ###

a, b = map(int, input().split())
print(a*b)
a, b = gets.chomp.split(" ")
a.to_i;	b.to_i
if a < b
    puts "a < b"
elsif a > b
    puts "a > b"
else
    puts "a == b"
end

### FIXED CODE ###

a,b=map(int, raw_input().split())

if a > b:
    print "a > b"
elif a < b:
    print "a < b"
else:
    print "a == b"
N=int(input())
for i in range(7):
  x=2**(i-0)
  if x<=N:
      max=max(x)
print(x)

### FIXED CODE ###

N=int(input())
for i in range(7):
  x=2**i
  if x<=N:
      max=2**i
print(max)
import fileinput


def solve_slimes(slimes):
    slime_union_table = [0] * len(slimes) * len(slimes)
    slime_cost_table = [0] * len(slimes) * len(slimes)

    for i in range(len(slimes)):
        slime_union_table[i] = slimes[i]

    for gap in range(1, len(slimes)):
        for li in range(len(slimes) - gap):
            split_size = slime_union_table[li] + slime_union_table[li + 1 + (gap - 1) * len(slimes)]
            slime_union_table[li + gap * len(slimes)] = split_size

            for split in range(0, gap):
                split_cost = slime_cost_table[li + split * len(slimes)] + slime_cost_table[li + split + 1 + (gap - split - 1) * len(slimes)] + split_size

                if slime_cost_table[li + gap * len(slimes)] == 0:
                    slime_cost_table[li + gap * len(slimes)] = split_cost

                else:
                    slime_cost_table[li + gap * len(slimes)] = min(
                        split_cost,
                        slime_cost_table[li + gap * len(slimes)]
                    )
    return slime_cost_table[len(slimes) * (len(slimes) - 1)]


inp = fileinput.FileInput()

inp.readline()
slimes = [int(v) for v in inp.readline().split()]

print(solve_slimes(slimes)

### FIXED CODE ###

import fileinput


def solve_slimes(slimes):
    slime_union_table = [0] * len(slimes) * len(slimes)
    slime_cost_table = [0] * len(slimes) * len(slimes)

    for i in range(len(slimes)):
        slime_union_table[i] = slimes[i]

    for gap in range(1, len(slimes)):
        for li in range(len(slimes) - gap):
            split_size = slime_union_table[li] + slime_union_table[li + 1 + (gap - 1) * len(slimes)]
            slime_union_table[li + gap * len(slimes)] = split_size

            for split in range(0, gap):
                split_cost = slime_cost_table[li + split * len(slimes)] + slime_cost_table[li + split + 1 + (gap - split - 1) * len(slimes)] + split_size

                if slime_cost_table[li + gap * len(slimes)] == 0:
                    slime_cost_table[li + gap * len(slimes)] = split_cost

                else:
                    slime_cost_table[li + gap * len(slimes)] = min(
                        split_cost,
                        slime_cost_table[li + gap * len(slimes)]
                    )
    return slime_cost_table[len(slimes) * (len(slimes) - 1)]


inp = fileinput.FileInput()

inp.readline()
slimes = [int(v) for v in inp.readline().split()]

print(solve_slimes(slimes))
a, p = [*map(int, input().split())]
print('{}'.format((a * 3 + p) // 2))

### FIXED CODE ###

a, p = list(map(int, input().split()))
print('{}'.format((a * 3 + p) // 2))
n=int(input())
dp=[[a,b,c] for i in range(n)]
dp[0]=[0,0,0]
for i in range(1,n):
    a,b,c=map(int,input().split())
    dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a
    dp[i][1]=max(dp[i-1][2],dp[i-1][0])+b
    dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c
print(max(dp[n-1]))


### FIXED CODE ###

n=int(input())
dp=[0,0,0]
for i in range(n):
    a,b,c=map(int,input().split())
    dp=[max(dp[1],dp[2])+a,max(dp[0],dp[2])+b,max(dp[0],dp[1])+c]
print(max(dp))
A, B, C = map(int, intput().split())
print(A^B^C)

### FIXED CODE ###

A, B, C = map(int, input().split())
print(A^B^C)
n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(n-2):
    if a[i] < a[i+1] < a[i+2] or a[i+2] < a[i+1] < a[i]
        cnt += 1
print(cnt)

### FIXED CODE ###

s = input()
a = []
for n in s:
    a.append(n)
if a.count(a[0]) == 2 and a.count(a[1]) == 2 and a.count(a[2]) == 2 and a.count(a[3]) == 2:
    print('Yes')
else:
    print('No')
i=input;i();l=i().split();x=1-('0'in l)
for j in l:
  x*=int(j);if x>1e18:x=-1;break
print(x)


### FIXED CODE ###

i = input
i()
x = 1
l = i().split()
if '0' in l:
    print(0)
    quit()
for j in l:
    x *= int(j)
    if x > 1e18:
        print(-1)
        quit()
print(x)
n=input()
lst=input().split()

cnt = 0
for i in range(0, len(lst)):
    m = i
    for j in range(i, len(lst)):
        if lst[m] > lst[j]:
            m = j
    if m != i:
        lst[i], lst[m] = lst[m], lst[i]
        cnt+=1

print " ".join(map(str,lst))
print (cnt)

### FIXED CODE ###

raw_input()
lst=map(int, raw_input().split())

cnt = 0
for i in range(0, len(lst)):
    m = i
    for j in range(i, len(lst)):
        if lst[m] > lst[j]:
            m = j
    if m != i:
        lst[i], lst[m] = lst[m], lst[i]
        cnt+=1

print " ".join(map(str,lst))
print (cnt)
import math
A,B,C = map(int, input().split())
K = int(input())
if A > B:
  K1 = math.ceil(math.log(A,B))
  B = B ** K1
  K1 = K1 -1
elif A == B:
  B = B ** 2
  K1 = 1
else:
  K1 = 0

if B > C:
  K2 = math.ceil(math.log(B,C)) - 1
elif B == C:
  K2= 1
else:
  K2= 0
  
if K1 + K2 <= K:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import math
A,B,C = map(int, input().split())
K = int(input())
if A > B:
  K1 = math.ceil(math.log(A/B,2))
  B = B * (2 ** K1)
  if A == B:
    B = B * 2
    K1 = K1 + 1
elif A == B:
  B = B * 2
  K1 = 1
else:
  K1 = 0

if B > C:
  K2 = math.ceil(math.log(B/C,2))
  C = C * (2 ** K2)
  if C == B:
    K2 = K2 + 1
elif B == C:
  K2= 1
else:
  K2= 0
  
if K1 + K2 <= K:
  print('Yes')
else:
  print('No')
S = input()
T = input()

for i in range(len(S) - len(T) + 1):
    flag = True
    for j in range(len(T)):
        if S[i+j] != T[j]:
            flag = False
    if flag:
        break
            
if flag:
    res = ''
    for i in range(len(S)):
        if S[i] == '?':
            res += 'a'
        else:
            res += S[i]
            
    print(res)
    
else:
    tmp = -1
    for i in range(len(S) - len(T) + 1):
        start = -1
        for j in range(len(T)):
            if S[i+j] == T[j] or S[i+j] == '?':
                start = i
            else:
                start = -1
                break
                
        
        if start != -1:
                tmp = i
    if tmp == -1:
        print('UNRESTORABLE')
    else:
        res = ''
        count = 0
        for i in range(len(S)):
            if tmp <= i < tmp + len(T):
                res += T[count]
                count += 1
            elif S[i] == '?':
                res += 'a'
            else:
                res += S[i]

        print(res)
                
            

### FIXED CODE ###

S = input()
T = input()


    
if True:
    tmp = -1
    for i in range(len(S) - len(T) + 1):
        start = -1
        for j in range(len(T)):
            if S[i+j] == T[j] or S[i+j] == '?':
                start = i
            else:
                start = -1
                break
                
        
        if start != -1:
                tmp = i
    if tmp == -1:
        print('UNRESTORABLE')
    else:
        res = ''
        count = 0
        for i in range(len(S)):
            if tmp <= i < tmp + len(T):
                res += T[count]
                count += 1
            elif S[i] == '?':
                res += 'a'
            else:
                res += S[i]

        print(res)
a = int(input())
b = int(input())

if a < b * 2:
    print(a - b * 2)
else:
    print(0)


### FIXED CODE ###

list = input().split()

a = int(list[0])
b = int(list[1])

if a > b * 2:
    print(a - b * 2)
else:
    print(0)
k=input()
x=k//2
if k%2==0:
  print(2*x*x)
else:
  print((2*x+1)*x)

### FIXED CODE ###

x = int(input())
y = x // 2
print(y*(x-y))
N = int(input())
A = map(int, input().split())

answer = [0] * len(A)
for i, Ai, in enumerate(A):
    answer[Ai - 1] = str(i + 1)
answer = ' '.join(answer)

print(answer)


### FIXED CODE ###

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

answer = [0] * N
for i, Ai, in enumerate(A):
    answer[Ai - 1] = str(i + 1)
answer = ' '.join(answer)

print(answer)
import math
X = int(input())
ruto = math.ceil(math.sqrt(2*X))+1
kari = ruto**2+ruto
for i in range(ruto-1, 0, -1):
    if i**2+i < 2*X:
        ans = i+1
        break
    kari = i**2+i
print(ans)


### FIXED CODE ###

import math
X = int(input())
ruto = math.ceil(math.sqrt(2*X))+1
kari = ruto**2+ruto
ans=1
for i in range(ruto-1, 0, -1):
    if i**2+i < 2*X:
        ans = i+1
        break
    kari = i**2+i
print(ans)
n=input()
a=[]
for i in range(len(n)):
  a.append(s[i])
print("Yes" if int(n)%sum(a)==0 else "No")


### FIXED CODE ###

n=input()
a=[]
for i in range(len(n)):
  a.append(int(n[i]))
print("Yes" if int(n)%sum(a)==0 else "No")
limit, sum_xyz = map(int, input().split())

pair = list()
x_bottom = sum_xyz - 2*limit
if x_bottom < 0:
    x_bottom = 0
else:
    x_bottom = x_bottom

for i in range(limit, x_bottom - 1, -1):
    x = i
    y_limit = 0
    if sum_xyz - x >= limit:
        y_limit = limit
    else:
        y_limit = sum_xyz - x
    y_bottom = sum_xyz - x - limit
    if y_bottom < 0:
        y_bottom = 0
    else:
        y_bottom = y_bottom

    for j in range(y_limit, y_bottom - 1, -1):
        y = j
        z = sum_xyz - x - y
        pair.append([x, y, z])
ans = len(pair)

print(ans)

### FIXED CODE ###

s = input()
result = s.replace(",", " ")

print(result)
n, t = list(map(input().split()))
data = []
for i in range(n):
    data.append(list(map(input().split())))
minCost = 1001
for i in range(n):
    if data[i][1] <= t:
        minCost = data[i][0]

if minCost == 1001:
    printf("TLE")
else:
    printf(minCost)

### FIXED CODE ###

n, t = list(map(int, input().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
minCost = 1001
for i in range(n):
    if data[i][1] <= t and minCost > data[i][0]:
        minCost = data[i][0]

if minCost == 1001:
    print("TLE")
else:
    print(minCost)
import sys
Q = int(input())
mod = 1000003
frac = [1]*1000003
for i in range(2,1000003):
    frac[i] = i * frac[i-1]%mod
for _ in range(Q):
    x, d, n = map(int, sys.stdin.readline().split())
    p = pow(d, mod-2, mod)*x % mod
    if d == 0:
        print(pow(x, n, mod))
    elif x == 0:
        print(0)
    elif p == 0:
        print(0)
        continue
    elif p + n - 1 >= mod:
        print(0)
        continue
    
    print(frac[p+n-1]*pow(frac[p-1], mod-2, mod)*pow(d, n, mod)%mod)

### FIXED CODE ###

import sys
Q = int(input())
mod = 1000003
frac = [1]*1000003
for i in range(2,1000003):
    frac[i] = i * frac[i-1]%mod
for _ in range(Q):
    x, d, n = map(int, sys.stdin.readline().split())
    p = pow(d, mod-2, mod)*x % mod
    if d == 0:
        print(pow(x, n, mod))
        continue
    elif x == 0:
        print(0)
        continue
    elif p == 0:
        print(0)
        continue
    elif p + n - 1 >= mod:
        print(0)
        continue
    
    print(frac[p+n-1]*pow(frac[p-1], mod-2, mod)*pow(d, n, mod)%mod)
# C - Typical Stairs

MOD = (10 ** 9) + 7
INF = float('inf')
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [INF] * (10 ** 5)

def f(i):
    if dp[i] != INF:
        return dp[i]
    else:
        if i in A:
            dp[i] = 0
        elif i < 2:
            dp[i] = 1
        else:
            dp[i] = (f(i - 1) + f(i - 2)) % MOD
        return dp[i]

print(f(N))


### FIXED CODE ###

# C - Typical Stairs

MOD = (10 ** 9) + 7
N, M = map(int, input().split())
A = [False] * (N + 1)
for _ in range(M):
    A[int(input())] = True
dp = [0] * (N + 1)
dp[0] = 1
if A[1] == False:
    dp[1] = 1

for i in range(2, N + 1):
    if A[i] == True:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[N])