Harryxun/stf_run huggingface dataset:
n = int(input())
x = input()


def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")


def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    solve = 0
    n_i = 2**(n-1)
    print(n_i)
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = (x_i % x_count) + (n_i % x_count)
        else:
            x_count -= 1
            solve = (x_i % x_count) - (n_i % x_count)
        n_i = n_i >> 1 
        count = 0

        if solve != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)


### FIXED CODE ###


n = int(input())
x = input()

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    x_i_t = x_i % (x_orig+1)
    if x_orig != 1:
        x_i_b = x_i % (x_orig-1)
    else:
        x_i_b = x_i
    solve = 0
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = x_i_t + pow(2,n-1-i,x_count)
        else:
            x_count -= 1
            if x_count != 0:
                solve = x_i_b - pow(2,n-1-i,x_count)
            else:
                print(0)
                continue
        count = 0

        if x_count != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)
#!/usr/bin/env python3

from collections import deque


def book(A, B, t, cnt):
    if len(A) == 0 and len(B) == 0:
        L.append(cnt)
        return cnt
    elif t == K:
        L.append(cnt)
        return cnt
    elif t > K:
        L.append(cnt-1)
        return cnt - 1

    a_r = 0
    b_r = 0
    if len(A) != 0:
        a = A.popleft()
        a_r = book(A, B, t+a, cnt+1)
        
    if len(B) != 0:
        b = B.popleft()
        b_r = book(A, B, t+b, cnt+1)
    L.append(a_r)
    L.append(b_r)
    return max(a_r, b_r)




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

L = []

A = deque(A)
B = deque(B)

t = 0
ret = 0

ret = book(A, B, 0, 0)

print(max(L))


### FIXED CODE ###

#!/usr/bin/env python3

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


a = [0]
b = [0]

for i in range(N):
    a.append(a[-1] + A[i])


for i in range(M):
    b.append(b[-1] + B[i])

ret = 0
j = M
for i in range(N+1):
    if a[i] > K:
        break
    while a[i] + b[j] > K:
        j -= 1

    ret = max(i+j, ret)


print(ret)
K = int(input())

ev = K//2
odd = k//2 + K%2
print(ev*odd)

### FIXED CODE ###

K = int(input())
 
ev = K//2
odd = K//2 + K%2
print(ev*odd)
from math import log2,ceil
from collections import defaultdict
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
cnt=defaultdict(lambda :0)

for i in range(n):
    temp=a[i]
    if temp==0:continue
    digit=log2(temp)
    for j in range(ceil(digit)+1):
        if (temp>>j)&1:
            cnt[j]+=1

#print(cnt)
ans=0
for digit,count in cnt.items():
    ans+=pow(2,digit)*count*(n-count)
print(ans%mod)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=tuple(map(int,input().split()))
mod=10**9+7
cnt=[0]*60

for temp in a:
    if temp==0:continue
    digit=len(bin(temp))-2
    for j in range(digit):
        if (temp>>j)&1:
            cnt[j]=cnt[j]+1

#print(cnt)
ans=0
for i in range(60):
    if cnt[i]==0:continue
    ans=(ans+pow(2,i)*cnt[i]*(n-cnt[i]))%mod
print(ans%mod)
n=int(input())
a=int(input())
b=int(input())
if n==1:print('Hello World')
elif n==2:print(a+b)

### FIXED CODE ###

n=int(input())
if n==1:print('Hello World')
else:
  a=int(input())
  b=int(input())
  print(a+b)
N, K = list(map(int, input().split()))
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -10**9-1
for i in range(N):
    cumsum = [0]*(N+1)
    seen = [-1]*N
    K_ = K
    now = i
    j = 0
    while K_ > 0 and seen[now] == -1:
        seen[now] = 1
        now = P[now]
        cumsum[j+1] = cumsum[j] + C[now]
        K_ -= 1
        j += 1
    if K_ == 0:
        ans = max(ans, max(cumsum[1:j+1]))
    else:
        if cumsum[j] > 0:
            loop_size = j
            loop_n = K//loop_size - 1
            tmp = loop_n*cumsum[loop_size]
            tmp += max(max(cumsum[1:loop_size]), cumsum[loop_size] + max(cumsum[1:K_%loop_size+1]))
            ans = max(ans, tmp)
        else:
            ans = max(ans, max(cumsum[1:j]))
print(ans)

### FIXED CODE ###

N, K = list(map(int, input().split()))
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -10**9-1
for i in range(N):
    cumsum = [0]*(N+1)
    seen = [-1]*N
    K_ = K
    now = i
    j = 0
    while K_ > 0 and seen[now] == -1:
        seen[now] = 1
        now = P[now]
        cumsum[j+1] = cumsum[j] + C[now]
        K_ -= 1
        j += 1
    if K_ == 0:
        ans = max(ans, max(cumsum[1:j+1]))
    else:
        if cumsum[j] > 0:
            loop_size = j
            loop_n = K//loop_size - 1
            tmp = loop_n*cumsum[loop_size]
            tmp += max(max(cumsum[1:loop_size+1]), cumsum[loop_size] + max(cumsum[0:K_%loop_size+1]))
            ans = max(ans, tmp)
        else:
            ans = max(ans, max(cumsum[1:j+1]))
print(ans)
import sys
read = sys.stdin.buffer.read#全部読み込むやつ
readline = sys.stdin.buffer.readline#1行読み込むやつ
readlines = sys.stdin.buffer.readlines#リストで読み込むらしい

N,K,*H = map(int,read().split())
N -= K
if N <= 0:
    print(0)
    exit()
    
for i in N:
    H.remove(max(H))
    
print(len(H))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read#全部読み込むやつ
readline = sys.stdin.buffer.readline#1行読み込むやつ
readlines = sys.stdin.buffer.readlines#リストで読み込むらしい

N,K,*H = map(int,read().split())
N -= K
if N <= 0:
    print(0)
    exit()
    
H.sort()
    
print(sum(H[: N]))
N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort()
tmp = A.pop(-1)
index = 0
for _ in range(M):
  tmp //= 2
  if tmp < A[-1]:
    A.append(tmp)
    tmp = A.pop(-2)
    A.sort()
A.append(tmp)

print(sum(A))

### FIXED CODE ###

import heapq

def minus_int(s):
  return -1 * int(s)

N, M = map(int, input().split())
A = list(map(minus_int, input().split()))
heapq.heapify(A)
for _ in range(M):
  tmp = int(heapq.heappop(A) / 2)
  heapq.heappush(A, tmp)

print(sum(A) * (-1))
h, w = map(int, input().split())
cells = []
cells.append(['0']*(w+2))
for i in range(h):
    l = [0]
    s = input().split()
    l+=list(s[0])
    l+=[0]
    cells.append(l)
cells.append([0]*(w+2))

is_ok = True
for i in range(1,len(cells)-1):
    for j in range(1,len(cells)-1):
        if cells[i][j] == '#':
            if cells[i-1][j] == '#':
                is_ok = True
            elif cells[i+1][j] == '#':
                is_ok = True
            elif cells[i][j-1] == '#':
                is_ok = True
            elif cells[i][j+1] == '#':
                is_ok = True
            else:
                is_ok = False
        if not is_ok:
            print("No")
            exit()
print("Yes")

### FIXED CODE ###

h, w = map(int, input().split())
cells = []
for i in range(h):
    s = input().split()
    cells.append(s[0])
ans = True
for i in range(1,h-1):
    for j in range(1,w-1):
        if cells[i][j] == '#':
            if cells[i-1][j] != '#' and cells[i+1][j] != '#' and cells[i][j-1] != '#' and cells[i][j+1] != '#':
                ans = False
                break
 
if ans: print("Yes")
else: print("No")
n = int(input())
    # print("n:",n)
    hl = []

    for i in range(n):
        hl.append(int(input()))
    #print(hl)

    #hl = [5, 5]
    #hl = [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
    # hl = [1,2,3,4,5]
    #hl = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

    i = 0
    ans = 1

    """
    for h in hl:
        d = i//4
        a = h-d
        if a<0:
            a=0
        ans += a
        i+=1
    """

    for i, h in enumerate(hl):  #return index, value
        d = i // 4
        a = h - d
        if a < 0:
            a = 0
        ans += a
    print(ans)

### FIXED CODE ###

# Edit: 2014/09/14
# Lang: Python3
# Time: .00s

if __name__ == "__main__":

    n = int(input())
    # print("n:",n)
    hl = []

    for i in range(n):
        hl.append(int(input()))
    # print(hl)

    # hl = [5, 5]
    # hl = [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
    # hl = [1,2,3,4,5]
    # hl = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

    i = 0
    d = 0
    ans = 1

    hl = sorted(hl, reverse=True)

    for i, h in enumerate(hl):  # return index, value
        #d = i // 4
        a = h - d
        if a < 0:
            a = 0
        ans += a
        if i % 4 == 3:
            d += 1
    print(ans)
    #print(type(ans))
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]"):
    a = sorted(A, reverse=True)
    bsum = 0
    p = []
    for day in range(M, -1, -1):

        rem = []

        for i, a_ in enumerate(a):
            if a_[0]==day:
                p.append(a_)
                rem.append(i)
            else:
                [a.pop(k) for k in rem] # 遅いかも
        
        # print("day : {}, a:{}, p:{}".format(day, a, p))
        if len(p)>0:
            # p = sorted(p, key = lambda x : x[1], reverse=True)
            p_max = max(p, key=lambda x: x[1])
            bsum += p_max[1]
            p.remove(p_max)
        

    print(bsum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = []

    for i in range(N):
        A.append((M-int(next(tokens)),int(next(tokens))))
    solve(N, M, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
import heapq

def solve(N: int, M: int, A: "List[int]"):
    a = sorted(A, reverse=False)
    a = deque(a)
    # ai(day) bi(reward)
    b_cands = []
    heapq.heapify(b_cands)

    ans = 0
    for M in range(M+1):
        while (len(a)!=0) and (a[0][0]==M):
            heapq.heappush(b_cands, -a.popleft()[1])
            # print(b_cands)
        if len(b_cands)>0:
            ans -= heapq.heappop(b_cands)

    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = []

    for i in range(N):
        A.append((int(next(tokens)),int(next(tokens))))
    solve(N, M, A)

if __name__ == '__main__':
    main()
n = int(input())

table = [[0 for i in range(10)] for j in range(10)]
for i in range(1, n+1):
    i = str(i)
    a, b = i[0], i[-1]
    table[a][b] += 1

ans = 0
for i in range(10):
    for j in range(10):
        ans += table[i][j] * table[j][i]

print(ans)


### FIXED CODE ###

n = int(input())

table = [[0 for i in range(10)] for j in range(10)]
for i in range(1, n+1):
    i = str(i)
    a, b = int(i[0]), int(i[-1])
    table[a][b] += 1

ans = 0
for i in range(10):
    for j in range(10):
        ans += table[i][j] * table[j][i]

print(ans)
r,D,x2000 = map(int,raw_input().split())
xi = x2000
for i in range(1,11):
    xi = r * xi - D
    print(xi)


### FIXED CODE ###

r,D,xi = map(int,input().split())
for i in range(10):
    xi = r * xi - D
    print(xi)
l = [int(i) for i in input().split()]
# sort()は破壊的じゃないです
l = l.sort
print(l[0]*10 + l[1] + l[2])

### FIXED CODE ###

l = [int(i) for i in input().split()]
# sort()は破壊的です
# sorted()は破壊的じゃないです
l.sort(reverse=True)
print(l[0]*10 + l[1] + l[2])
N = int(input())
A = [int(i) for i in input().split()]

while len(A) > 1:
  min_num = min(A)
  min_index = A.index(min(A))
  for i in range(len(A)):
    if i != min_index:
      A[i] = A[i] % min_num
      if(A[i] == 0):
        A.pop(i)


print(A[0])

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

while len(A) > 1:
  min_num = min(A)
  min_index = A.index(min(A))
  for i in range(len(A)):
    if i != min_index:
      A[i] = A[i] % min_num

  while 0 in A:
    A.remove(0)

print(A[0])
n = int(input())

s = input()
a = []
for i in range(n - 1):
    a.append(abs(int(s[i]) - int(s[i + 1])))

ans = []
    if (n - 2)^ r ^ (n - 2 - r) == 0:
        ans.append(int(a[r]))
res = 0

for i in ans:
    res = abs(res - i)
if 1 in a:
    print(res % 2)
else:
    print(res)

### FIXED CODE ###

n = int(input())

s = input()
a = []
for i in range(n - 1):
    a.append(abs(int(s[i]) - int(s[i + 1])))

ans = []
for r in range(n - 1):
    if (n - 2)^ r ^ (n - 2 - r) == 0:
        ans.append(int(a[r]))
res = 0

for i in ans:
    res = abs(res - i)
if 1 in a:
    print(res % 2)
else:
    print(res)
n = int(input())
z = [list(map(int,input().split())) for _ in range(n)]

def set_height(i,x,y):
	ans = z[i][2] + abs(z[i][0] - x) + abs(z[i][1] - y)
	return ans


answer = 0
for j in range(0,101):
	for k in range(0,101):
		answer=set_height(0,j,k)
		flag = 1
		for l in range(1,n):
			if answer!= set_height(l,j,k):
				flag = 0
				break
		if flag == 1 && answer <= 10**9:
			test = map(str,(j,k,answer))
			print(" ".join(test))


### FIXED CODE ###

n = int(input())
z = [list(map(int,input().split())) for _ in range(n)]


def set_height(i,x,y):
	ans = z[i][2] + abs(z[i][0] - x) + abs(z[i][1] - y)
	return ans


answer = 0
for j in range(0,101):
	for k in range(0,101):
		flag = 1
		for l in range(0,n):
			if z[l][2] != 0:
				answer = set_height(l,j,k)
				break

		for l in range(0,n):
			if z[l][2] == 0:
				if answer > set_height(l,j,k):	
					flag = 0
					break
			else:
				if answer != set_height(l,j,k):
					flag = 0
					break
		if flag == 1 and answer > 0 :
			test = map(str,(j,k,answer))
			print(" ".join(test))
w,h,n=map(int,input().split())

ma_x=w
ma_y=h
mi_x=0
mi_y=0

for i in range(n):
    x,y,a=map(int,input().split())
    if a==1:
        if mi_x<x:
            mi_x=x
    elif a==2:
        if ma_x>x:
            ma_x=x
    elif a==3:
        if mi_y<y:
            mi_y=y
    elif a==4:
        if ma_y>y:
            ma_y=y

if ma_x-mi_x<0 and ma_y-mi_y<0:
  ma_x-mi_x=0
            
ans=(ma_x-mi_x)*(ma_y-mi_y)

if ans<0:
    ans=0

print(ans)

### FIXED CODE ###

w,h,n=map(int,input().split())

ma_x=w
ma_y=h
mi_x=0
mi_y=0

for i in range(n):
    x,y,a=map(int,input().split())
    if a==1:
        if mi_x<x:
            mi_x=x
    elif a==2:
        if ma_x>x:
            ma_x=x
    elif a==3:
        if mi_y<y:
            mi_y=y
    elif a==4:
        if ma_y>y:
            ma_y=y

if ma_x-mi_x<0 and ma_y-mi_y<0:
  ma_x=mi_x
            
ans=(ma_x-mi_x)*(ma_y-mi_y)

if ans<0:
    ans=0

print(ans)
N=Input()
if N%2=0:
    print(N/2)
else:
    print((N+1)/2)

### FIXED CODE ###

N=int(input())

if N%2==0:
    print(N//2)

else:
    print((N+1)//2)
def check():
  n = int(input())
  if n <= 9:
    return 'Yes'
  elif n > 81:
    return 'No'
  else:
    for i in range(2, 9):
      q, mod = divmod(n, i)
      if mod == 0 and q <= 9:
        return 'Yes'
    return 'No'

print(check())


### FIXED CODE ###

a, b = map(int, input().split())
if a < 10 and b < 10:
  print(a * b)
else:
  print(-1)
import math

N,X = map(int,input().split())
x = list(map(int,input().split()))
distance = []

for i in x:
    distance.append(abs(i-X))



### FIXED CODE ###

A,B = map(int, input().split())
if A * B % 2 == 0:
    print("No")
else:
    print("Yes")
M=[0,1,-1,0,0,1,1,2,3,3,4,4]
def L(y,m):
  if m<=2: y-=1
  return y/4-y/100+y/400+M[m]

while 1:
  x=map(int,raw_input().split(" "))
  if any([e<0 for e in x]): break
  a,b,c,d,e,f=x
  ans=(d-a)*365+(e-b)*30+f-c+L(d,e)-L(a,b)  
  print ans

### FIXED CODE ###

import datetime as D
while 1:
  a,b,c,d,e,f=map(int,raw_input().split())
  try: print (D.date(d,e,f)-D.date(a,b,c)).days
  except: break
N = int(input())
D = []
count = 0

for n in range(N):
    input_line = input().split()
    if (int(input_line[0]) == int(input_line[1])):
        count += 1
    else:
        pass

if count >= 3:
        print(Yes)

else:
        print(No)

### FIXED CODE ###

N = int(input())
D = []
count, temp = 0, 0

for n in range(N):
    input_line = input().split()
    if (int(input_line[0]) == int(input_line[1])):
        count += 1
        if count == 3:
            temp = 1
    elif(temp ==1):
        break
    else:
        count = 0

if count >= 3:
        print('Yes')

else:
        print('No')
N = int(input())
A = list(map(int, input().split()))

mod = 10**9+7

LCM = A[0]
for i in range(N-1):
  LCM = lcm(LCM, A[i+1])

ans = 0
for a in A:
  ans += LCM // a
  ans %= mod

print(ans)

### FIXED CODE ###

import math

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

mod = 10**9+7

def lcm(x, y):
  return (x // math.gcd(x, y)) * y

LCM = A[0]
for i in range(N-1):
  LCM = lcm(LCM, A[i+1])

LCM %= mod

ans = 0
for a in A:
  ans += LCM * pow(a, mod-2, mod) % mod
  ans %= mod

print(ans)
n,k=map(int,input().split())
ar=list(map(int,input().split()))
for i in range(k,n):
	if ar[i]>ar[i-k]:
		print("Yes")
	else:
		print("No"

### FIXED CODE ###

n,k=map(int,input().split())
ar=list(map(int,input().split()))
for i in range(k,n):
	if ar[i]>ar[i-k]:
		print("Yes")
	else:
		print("No")
K, S = input().split()
K = int(k)

if len(s) <= k:
    print(s)
else:
    print(s[0:k] + '...')

### FIXED CODE ###

K = int(input())
S = input()

if len(S) <= K:
    print(S)
else:
    S = S[0:K]+"..."
    print(S)
import math

a=int(input())

S=round(a*a*math.pi,6)
R=round(a*2*math.pi,6)

print(S,R)

### FIXED CODE ###

import math

r=float(input())

s=r*r*math.pi
l=2*r*math.pi

print(s,l,sep=" ")
a,b,c = map(int.input().split())
if a=b and b=c:
  print(1)
elif (a=b or b=c or a=c):
  print(2)
else:
  print(3)


### FIXED CODE ###

a,b,c = map(int,input().split())
if a==b and b==c:
  print(1)
elif a==b or b==c or a==c:
  print(2)
else:
  print(3)
A, B, C = map(int, input().split())
K= int(input()) 
 
 
if (B**K>A)&(C>B):
  print("Yes")
elif (B**(K-1)>A)&(C>B**1) :
  print("Yes")
elif (B**(K-2)>A)&(C>B**2) :
  print("Yes")
elif (B**(K-3)>A)&(C>B**3) :
  print("Yes")
elif (B**(K-4)>A)&(C>B**4) :
  print("Yes")
elif (B**(K-5)>A)&(C>B**5) :
  print("Yes")
elif (B**(K-6)>A)&(C>B**6) :
  print("Yes")
elif (B>A)&(C>B**7) :
  print("Yes")
else :
  print("No")

### FIXED CODE ###

s = int(input()) 
 
if 400 <= s <= 599:
  print("8")
elif  600 <= s <=799:
        print("7")
elif  800 <= s <=999:
        print("6")
elif  1000 <= s <=1199:
        print("5")
elif  1200 <= s <=1399:
        print("4")
elif  1400 <= s <=1599:
        print("3")
elif  1600 <= s <=1799:
        print("2")
elif  1800 <= s <=1999:
        print("1")
n = int(input())
pros = [ int(input()) for i in range(n)]
k = set()
for i in range(1 << len(pros)):
    output = []
    for j in range(len(pros)):
        if ((i >> j) & 1) == 1:
            output.append(pros[j])
    if sum(output) % 10 != 0:
        k.add(sum(output))
print(max(k))

### FIXED CODE ###

n = int(input())
s = [int(input()) for i in range(n)]
s.sort()
j = sum([ i % 10 for i in s ])
if j == 0:
    ans = 0
else:
    if sum(s) % 10 != 0:
        ans = sum(s)
    else:
        for i in range(n):
            tmp = sum(s)-s[i]
            if tmp % 10 != 0:
                ans = tmp
                break
print(ans)
l = input().split()
a = int(l[0])
b = int(float(l[1])*100.)
ans = a * b
aans = str(ans)[:-2]

print(int(aans))

### FIXED CODE ###

a, b = input().split()

a = int(a)
b = int(b.replace(".", ""))

if a * b >= 100:
    print(str(a*b)[:-2])
else:
    print(0)
import sys
input=sys.stdin.readline
mod=1000003
m=mod-1
def modinv(n):
    return pow(n,mod-2,mod)
Fact=[1] #階乗
for i in range(1,m+1):
    Fact.append(Fact[i-1]*i%mod)
Finv=[0]*(m+1) #階乗の逆元
Finv[-1]=modinv(Fact[-1])
for i in range(m-1,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    return Fact[n]*Finv[r]*Finv[n-r]%mod
q=int(input())
for _ in range(q):
    x,d,n=map(int,input().split())
    f=Fact[n]
    r=(x*modinv(d))%mod+n-1
    c=comb(r,n)
    p=pow(d,n,mod)
    print((f*c*p)%mod)

### FIXED CODE ###

import sys
input=sys.stdin.readline
mod=1000003
m=mod-1
def modinv(n):
    return pow(n,mod-2,mod)
Fact=[1]
for i in range(1,m+1):
    Fact.append(Fact[i-1]*i%mod)
Finv=[0]*(m+1)
Finv[-1]=modinv(Fact[-1])
for i in range(m-1,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%mod

def query(x,d,n):
    if x==0:
        return 0
    if d==0:
        return pow(x,n,mod)
    k=(x*modinv(d))%mod
    if k+n-1>=mod:
        return 0
    ans=Fact[k+n-1]*Finv[k-1]%mod
    ans*=pow(d,n,mod)
    ans%=mod
    return ans

q=int(input())
for _ in range(q):
    x,d,n=map(int,input().split())
    print(query(x,d,n))
import numpy as np
from numpy.random import *

def quicksort(array):
    if len(array) < 2:
        return array # ?????¬??±??????
    else:
        pivot = array[0] # ?????°??±??????
        # ???????????????????°???????????????????????????¨?????????
        less = [i for i in array[1:] if i <= pivot]

        # ????????????????????§??????????????????????????¨?????????
        greater = [i for i in array[1:] if i > pivot]

        return quicksort(less) + [pivot] + quicksort(greater)


array = randint(0, 1000, 10) 
sorted_array = quicksort(array)
print(sorted_array[0:3])

### FIXED CODE ###

array = []
for _ in range(10):
    array.append(int(input()))

sorted_array = sorted(array,reverse=True)
for i in range(3):
    print(sorted_array[i])
N = input().split()
list = []

for i in range(1,int(N[0]),1):
    list.append(input())

list.sort(reverse = False)

ans = ""
for i in range(1,N+1,1):
    ans = ans + list[0]
    list.pop(0)

print(ans)


### FIXED CODE ###

N = input().split()
list = []

N = int(N[0])
for i in range(1,N+1,1):
    list.append(input())

list.sort(reverse = False)

ans = ""
for i in range(1,N+1,1):
    ans = ans + list[0]
    list.pop(0)

print(ans)
S = int(input())
h = S // 3600
ms = S % 3600
m = ms // 60
s = ms % 60
print(h + ":" + m + ":" + s)

### FIXED CODE ###

S = int(input())
s = str(S % 60)
HM = S // 60
m = str(HM % 60)
h = str(HM // 60)
print(h + ":" + m + ":" + s)
n=int(input())
g=[[] for i in range(n)]
ro=[0]*n
c=list(map(int,input().split()))
c.sort(reverse=True)
for i in range(n-1):
    a,b=map(int,input().split())
    ro[a-1]+=1
    ro[b-1]+=1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
m=max(ro)
mi=ro.index(m)
q=[mi]
ans=[0]*n
v=[0]*n
v[mi]=1
ans[mi]=c.pop()
while len(q)>0:
    s=q.pop()
    for i in g[s]:
        if v[i]==0:
            v[i]=1
            ans[i]=c.pop()
            q.append(i)
print(sum(c)-max(c))
print(*ans)
            

### FIXED CODE ###

n=int(input())
g=[[] for i in range(n)]
ro=[0]*n
for i in range(n-1):
    a,b=map(int,input().split())
    ro[a-1]+=1
    ro[b-1]+=1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
c=list(map(int,input().split()))
c.sort(reverse=True)
m=max(ro)
mi=ro.index(m)
q=[mi]
ans=[0]*n
v=[0]*n
v[mi]=1
ans[mi]=c.pop(0)
while len(q)>0:
    s=q.pop()
    for i in g[s]:
        if v[i]==0:
            v[i]=1
            ans[i]=c.pop(0)
            q.append(i)
print(sum(ans)-max(ans))
print(*ans)
s = list(input())
count = 0
for i in range(1,n):
  if s[i] == s[i-1]:
    if s[i] == "0":
      s[i] = "1"
    else:
      s[i] = "0"
    count += 1
print(count)

### FIXED CODE ###

s = list(input())

count = 0
for i in range(1,len(s)):
  if s[i] == s[i-1]:
    if s[i] == "0":
      s[i] = "1"
    else:
      s[i] = "0"
    count += 1
    
print(count)
n = int(input())
S = {input() for 0 in range(n)}
ans = len(S)
print(ans)


### FIXED CODE ###

n = int(input())
S = {input() for i in range(n)}
ans = len(S)
print(ans)