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

n = int(input())
l = 0
s = []
for i in range(20):
	print(l)
	stemp = str(input())
	s.append(stemp)
	if stemp[i] == 'Vacant':
		break
	elif i!=0:
		if s[i] == s[i-1]:
			if ((n-l)//2)%2 == 0:
				l = (n-l)//2
			else:
				l = (n-l)//2+1
		else:
			if l%2 == 0:
				l = l//2
				s[i] = s[i-1]
			else:
				l = l//2+1
				s[i] = s[i-1]
	elif i==0:
		if (n//2)%2==0:
			l = l+n//2
		else:
			l = l+(n//2)+1

### FIXED CODE ###

n = int(input())
l = 0
s = []
start = [0]
end = [n]
check = 1

for i in range(20):
	print(l)
	stemp = str(input())
	s.append(stemp)
	if stemp == 'Vacant':
		break
	elif i!=0:
		if check == 1:
			if s[i-1] == s[i]:
				start[0] = l
				if ((end[0]-start[0])//2)%2==0:
					l = start[0]+(end[0]-start[0])//2
				else:
					l = start[0]+(end[0]-start[0])//2+1
				
			else:
				end[0] = l
				if ((end[0]-start[0])//2)%2==0:
					l = start[0]+(end[0]-start[0])//2
				else:
					l = start[0]+(end[0]-start[0])//2+1
				check = check*-1

		elif check == -1:
			if s[i-1] == s[i]:
				end[0] = l
				if ((end[0]-start[0])//2)%2==0:
					l = start[0]+(end[0]-start[0])//2
				else:
					if abs((end[0]-start[0])) == 2:
						l = start[0]+(end[0]-start[0])//2
					else:
						l = start[0]+(end[0]-start[0])//2-1
				
			else:
				start[0] = l
				if ((end[0]-start[0])//2)%2==0:
					l = start[0]+(end[0]-start[0])//2
				else:
					l = start[0]+(end[0]-start[0])//2+1
				check = check*-1
	else:
		if (n//2)%2==0:
			l = l+n//2
		else:
			l = l+(n//2)+1
### BUGGY CODE ###

from collections import Counter

anagrams = []
for _ in range(int(input())):
    count = Counter(input())
    found = False
    for v in anagrams:
        if v["count"] == count:
            found = True
            v["total"] += 1
            break
    if not found:
        anagrams.append({"count": count, "total": 1})

total = 0
for v in anagrams:
    n = v["total"]
    total += n * (n - 1) / 2

print(int(total))


### FIXED CODE ###

from collections import defaultdict

anagrams = defaultdict(int)
for _ in range(int(input())):
    anagrams[str(sorted(input()))] += 1

total = 0
for k, v in anagrams.items():
    total += v * (v - 1) / 2

print(int(total))
### BUGGY CODE ###

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

result = []
for i in range(1, N+1):
    result.append(A.index(i) + 1)
print(*result)


### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))

result = np.argsort(A) + 1

print(*result)
### BUGGY CODE ###

import sys
import numpy as np 
def minimize():
    L, R=map(int,input().split())
    lis=[]
    for i in range(L,R):
        for j in range(i+1, R+1):
            x=(i*j) %2019
            lis.append(x)
    lis=np.array(lis)
    ans=lis.min()
    print(ans)

minimize()


### FIXED CODE ###

import sys
import numpy as np 
def minimize():
    L, R=map(int,input().split())
    lis=[]
    if (L+2019) >= R:
        
        for i in range(L,R):
            for j in range(i+1, R+1):
                x=(i*j) %2019
                lis.append(x)
        lis=np.array(lis)
        ans=lis.min()
        print(ans)
    
    else :
        for i in range(L,(L+2019)):
            for j in range(i+1, L+2020):
                x=(i*j) %2019
                lis.append(x)
        lis=np.array(lis)
        ans=lis.min()
        print(ans)


minimize()
### BUGGY CODE ###

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    h, w = input_int_list()
    grid = []
    grid.append(["@"] * (w + 2))
    for _ in range(h):
        grid.append(["@"] + list(input()) + ["@"])
    grid.append(["@"] * (w + 2))

    # 幅優先探索で すべてを"#"に変える。
    # かかった手数分が答え
    cnt = 1
    direction = ((0, 1), (1, 0), (-1, 0), (0, -1))
    while True:
        do_swap = False
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                if grid[i][j] == "#" or grid[i][j] == cnt - 1:
                    for di, dj in direction:
                        if grid[i + di][j + dj] == ".":
                            do_swap = True
                            grid[i + di][j + dj] = cnt
                    grid[i][j] = "@"
        if do_swap:
            cnt += 1
        else:
            break

    print(cnt - 1)

    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    from collections import deque

    h, w = input_int_list()
    grid = []
    visited = []
    grid.append(["@"] * (w + 2))
    visited.append([True] * (w + 2))
    for _ in range(h):
        grid.append(["@"] + list(input()) + ["@"])
        visited.append([True] + [False] * w + [True])
    grid.append(["@"] * (w + 2))
    visited.append([True] * (w + 2))

    # 幅優先探索で すべてを"#"に変える。
    # かかった手数分が答え
    direction = ((0, 1), (1, 0), (-1, 0), (0, -1))
    dq = deque()
    # すべての"#"をdequeに入れる
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if grid[i][j] == "#":
                dq.append((i, j, 0))
                visited[i][j] = True
    ans = 0
    # 幅優先探索
    while dq:
        i, j, d = dq.popleft()
        for di, dj in direction:
            if grid[i + di][j + dj] == "." and not visited[i + di][j + dj]:
                dq.append((i + di, j + dj, d + 1))
                visited[i + di][j + dj] = True
                ans = max(ans, d + 1)

    print(ans)
    return


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

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    dp = [0] * (N + 1)
    ans = 0

    for i in range(N - 1, -1, -1):
        for j in range(i + 1, N):
            if S[i] == S[j]:
                dp[j] = dp[j + 1] + 1
                if ans < min(dp[j], j - i):
                    ans = min(dp[j], j - i)
            else:
                dp[j] = 0

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    ans = 0
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for j in range(N - 1, i - 1, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
            if ans < min(j - i, dp[i][j]):
                ans = min(j - i, dp[i][j])

    print(ans)
    return


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

s = input()
t = input()
m = len(s)
n = len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
res = ""
while n != 0 and m != 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        n -= 1
        m -= 1
        res = s[m] + res
print(res)

### FIXED CODE ###

s = input()
t = input()
m = len(s)
n = len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        x = s[i-1]
        y = t[j-1]
        if x == y:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = dp[i-1][j]
            if dp[i][j] < dp[i][j-1]:
                dp[i][j] = dp[i][j-1]
res = ""
while n != 0 and m != 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        n -= 1
        m -= 1
        res = s[m] + res
print(res)
### BUGGY CODE ###

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

A_set = set(A)

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

ans_d = {}
for a_s in A_set:
	#print(A.count(a))
	ans_d[str(a_s)] = A.count(a_s)

for a in A:
    A_new = ans_d.copy()
    A_new[str(a)] -= 1
    ans = 0
    #print(A_new)
    #print("="*10)
    for a_n in A_new.values():
        if a_n <= 1:
            continue
        else:
            ans += cmb(a_n, 2)
    print(ans)

### FIXED CODE ###

import sys
from collections import Counter

def cmb2(n):
	if n < 2:
		return 0

	return n * (n-1) // 2

if __name__ == "__main__":

	N = int(input())
	A = [int(i) for i in input().split()]
	# A = list(map(int, input().split()))

	c = Counter(A)
	s = 0
	for v in c.values():
		s += cmb2(v)

	for a in A:
		print(s - cmb2(c[a]) + cmb2(c[a] - 1))
### BUGGY CODE ###

from collections import deque

N = int(input())
graph = [[] for _ in range(N+1)] #木構造を入れておく
long = [0] * (N+1) #Kから任意のノードまでの距離

for i in range(N-1):
  x, y, z = map(int, input().split())
  graph[x].append([y, z])
  graph[y].append([x, z])
  
Q, K = map(int, input().split())
x = list()
y = list()

for i in range(Q):
  x_i, y_i = map(int, input().split())
  x.append(x_i)
  y.append(y_i)

  
for i in range(1,N+1): #Kから任意のノードまでの距離を求める
  q = deque([K])
  while q:
    t = q.popleft()
    for i in range(len(graph[t])):
      next_t = graph[t][i][0]
      if(long[next_t] > 0):
        continue
        
      else:
        q.append(next_t)
        long[next_t] = long[t] + graph[t][i][1]
        

for i in range(Q):
  ans = long[x[i]] + long[y[i]]
  print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
X = []
ans = 1
for i in range(K):
    ans = ans*A[i]
X.append(ans)

for i in range(K+1,N+1):
    ans = (ans//A[i-1-K])*A[i-1]
    X.append(ans)
for i in range(N-K):
    if X[i] < X[i+1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(K,N):
    if A[i] > A[i-K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#B
N = int(input())
A = list(sorted(map(int,input().split())))
ans=1
if A[0]==0:
  print(0)
else:
  for i in A:
    ans*=i
  if ans > 10**18:
    print(-1)
  else:
    print(ans)

### FIXED CODE ###

#B
N = int(input())
A = list(sorted(map(int,input().split())))
ans=1
if A[0]==0:
    print(0)
else:
    for i in A:
        ans*=i
        if ans > 10**18:
            ans =-1
            break
    print(ans)
### BUGGY CODE ###

N = int(input())

def f(n):
    print(n)
    S = input()
    if S == 'Vacant':
        exit()
    return S

l = 0
r = N - 1
S = f(l)
U = f(r)
for i in range(20):
    mid = (l + r) // 2
    U = f(mid)
    len = m - l + 1
    if ((len % 2) ^ (S == U)):
        r = mid
        S = U
    else:
        l = mid


### FIXED CODE ###

N = int(input())

def f(n):
    print(n, flush = True)
    S = input()
    if S == 'Vacant':
        exit()
    return S

l = 0
r = N
S = f(l)
for i in range(20):
    mid = (l + r) // 2
    U = f(mid)
    len = mid - l + 1
    if (len % 2 == 0 and S != U) or (len % 2 and S == U):
        l = mid
        S = U
    else:
        r = mid
### BUGGY CODE ###

n, m = map(int, input().split())

nums = list(map(int, input().split()))

for i in range(m):
    b, c = map(int, input().split())
    for j in range(b):
        nums.append(c)

count = 0
result = 0
for i in sorted(nums, reverse=True):
    if count >= n:
        break
    result = result + i
    count = count + 1

print(result)

### FIXED CODE ###

n, m = map(int, input().split())

nums = list(map(int, input().split()))

ops = []
for i in nums:
    ops.append([1, i])
    
for i in range(m):
    b, c = map(int, input().split())
    ops.append([b, c])

total = 0
sums = []
for b, c in sorted(ops, key=lambda x:x[1], reverse=True):
    if total > n:
        break
    sums.extend([c]*b)
    total = total + b
print(sum(sums[:n]))
### BUGGY CODE ###

k = int(input())
num = input().split()

ass = 0

for i in range(k):
    for j in range(i+1,k):
        n1 = int(num[i]) % (10**9 + 7)
        n2 = int(num[j]) % (10**9 + 7)
        n3 = n1 * n2
        ass += n3
        ass = ass % (10**9 + 7)
    ass = ass % (10**9 + 7)


ans = ass % (10**9 + 7)
print(ans)

### FIXED CODE ###

k = int(input())
num = input().split()

l = 0
ass = 0
ans = 0

for i in range(k):
    l += int(num[i])

for i in range(k):
    l -= int(num[i])
    ass += int(num[i]) * l
    

ans = ass % (10**9 + 7 )
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

print(*ans)






### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

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

import sys
sys.setrecursionlimit(10**6)
n,A,B,C=map(int,input().split())
s=[input() for i in range(n)]
def dfs(d,a,b,c,now):
    global n,s
    if d==n:
        print("Yes")
        for i in range(n):
            print(now[i])
        sys.exit()
    else:
        if s[d][0]=="A" and s[d][1]=="B":
            if a>0:
                dfs(d+1,a-1,b+1,c,now+"B")
            if b>0:
                dfs(d+1,a+1,b-1,c,now+"A")
        elif s[d][0]=="A" and s[d][1]=="C":
            if a>0:
                dfs(d+1,a-1,b,c+1,now+"C")
            if c>0:
                dfs(d+1,a+1,b,c-1,now+"A")
        else:
            if b>0:
                dfs(d+1,a,b-1,c+1,now+"C")
            if c>0:
                dfs(d+1,a,b+1,c-1,now+"B")

dfs(0,A,B,C,"")
print("No")

### FIXED CODE ###

n,a,b,c=map(int,input().split())
s_=[input() for i in range(n)]
ans=""
for i in range(n):
    s1,s2=s_[i]
    if s2=="B":
        if a==1 and b==1 and i!=n-1:
            if s_[i+1][0]=="A":
                a,b,ans=(a+1,b-1,ans+"A")
            else:
                a,b,ans=(a-1,b+1,ans+"B")
            continue
        a,b,ans=(a-1,b+1,ans+"B") if a>b else (a+1,b-1,ans+"A")
        if min(a,b)==-1:
            print("No")
            break
    elif s1=="A":
        if a==1 and c==1 and i!=n-1:
            if s_[i+1][1]=="C":
                a,c,ans=(a-1,c+1,ans+"C")
            else:
                a,c,ans=(a+1,c-1,ans+"A")
            continue
        a,c,ans=(a-1,c+1,ans+"C") if a>c else (a+1,c-1,ans+"A")
        if min(a,c)==-1:
            print("No")
            break
    else:
        if c==1 and b==1 and i!=n-1:
            if s_[i+1][1]=="C":
                b,c,ans=(b-1,c+1,ans+"C")
            else:
                b,c,ans=(b+1,c-1,ans+"B")
            continue
        b,c,ans=(b-1,c+1,ans+"C") if b>c else (b+1,c-1,ans+"B")
        if min(b,c)==-1:
            print("No")
            break
else:
    print("Yes")
    for j in range(n):
        print(ans[j])
### BUGGY CODE ###

N = int(input())
S = input()
Q = int(input())

seg = [set([]) for _ in range(2*N-1)]
def update(k, x):
    k += N-1
    seg[k] = set([x])
    while k:
        k = (k-1)//2
        seg[k] = seg[2*k+1] | seg[2*k+2]
        
def query(p, q):
    p += N-1
    q += N-2
    res = set([])
    while q-p > 1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res |= seg[q]
    else:
        res |= seg[p] | seg[q]
    return len(res)

for i in range(N):
    update(i, S[i])
    
for _ in range(Q):
    a,b,c = map(str, input().split())
    if a == "1":
        update(int(b)-1, c)
    else:
        print(query(int(b)-1, int(c)))

### FIXED CODE ###

N = int(input())
S = input()

seg = [0]*(2*N-1)

def update(k, x):
    k += N-1
    seg[k] = 2**x
    while k:
        k = (k-1)//2
        seg[k] = seg[2*k+1] | seg[2*k+2]
        
def query(p, q):
    p += N-1
    q += N-2
    res = 0
    while q-p > 1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res |= seg[q]
    else:
        res |= seg[p] | seg[q]
    return bin(res).count("1")

def f(s):
    return ord(s) - ord("a") + 1

for i in range(N):
    update(i, f(S[i]))
    
Q = int(input())
for _ in range(Q):
    a,b,c = map(str, input().split())
    if a == "1":
        update(int(b)-1, f(c))
    else:
        print(query(int(b)-1, int(c)))
### BUGGY CODE ###



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]

n =int(input())
ans = 0
for i in range(1,n+1,1):
    ans += i*len(make_divisors(i))


print(ans)


### FIXED CODE ###


n =int(input())

sum = 0
for i in range (1,n+1,1):
    k= n//i
    sum += int(i*k*(k+1)/2)

print(sum)
### BUGGY CODE ###

n=int(input())
import sys
sys.setrecursionlimit(1000000)
def kaijo(n):
    if n==0:
        return(1)
    else:
        n=n%(10**9+7)
        return(n*kaijo(n-1))
print(kaijo(n)%(10**9+7))


### FIXED CODE ###

n=int(input())
'''
import sys
sys.setrecursionlimit(1000000)
def kaijo(n):
    if n==0:
        return(1)
    else:
        n=n%(10**9+7)
        return(n*kaijo(n-1))
print(kaijo(n)%(10**9+7))
'''
ans=1
for i in range(1,n+1):
    ans=i*(ans%(10**9+7))
print(ans%(10**9+7))
### BUGGY CODE ###

mod = 10**6 + 3

fac = [0]*mod
fac[0] = 1
for i in range(1, mod):
    fac[i] = fac[i - 1] * i
    fac[i] %= mod

def gcd(a, b):
    def calc(a, b, first, second):
        if a < b:
            a, b = b, a
        r = a % b
        q = -(a - r)/b
        if r == 0:
            return b, second
        # first += q * second
        first = [x + q * y for (x, y) in zip(first, second)]
        return calc(r, b, second, first)
    first = [1, 0]
    second = [0, 1]
    return calc(a, b, first, second)

def inverse(n, mod):
    table = gcd(n, mod)
    inv = table[1][1]
    if inv < 0:
        inv += mod
    return inv

def mod_pow(x, n, mod):
    ret = 1
    while n > 0:
        if n & 1 != 0:
            ret *= x
        x *= x
        n >>= 1
    return ret

l = raw_input().split()
Q = int(l[0])
X = []
D = []
N = []
for i in range(Q):
    l = raw_input().split()
    X.append(int(l[0]))
    D.append(int(l[1]))
    N.append(int(l[2]))


for i in range(Q):
    x = X[i]
    d = D[i]
    n = N[i]
    if d == 0:
        print(mod_pow(x, n, mod))
        continue
    inv_d = inverse(d, mod)
    x_d = (x * inv_d) % mod
    d_n = mod_pow(d, n, mod)
    # print(i, x, d, n, inv_d, x_d, x_d + n - 1, d_n)
    if x_d + n - 1 >= mod:
        print(0)
        continue
    ans1 = fac[(x_d + n - 1) % mod]
    ans2 = fac[x_d - 1]
    # print(ans1, ans2)
    ans = ans1 * inverse(ans2, mod)
    ans %= mod
    ans = ans * d_n
    ans %= mod
    print(ans)

### FIXED CODE ###

mod = 10**6 + 3

fac = [0]*mod
fac[0] = 1
for i in range(1, mod):
    fac[i] = fac[i - 1] * i
    fac[i] %= mod

def gcd(a, b):
    def calc(a, b, first, second):
        if a < b:
            a, b = b, a
        r = a % b
        q = -(a - r)//b
        if r == 0:
            return b, second
        # first += q * second
        first = [x + q * y for (x, y) in zip(first, second)]
        return calc(r, b, second, first)
    first = [1, 0]
    second = [0, 1]
    return calc(a, b, first, second)

def mod_inv(n, mod):
    table = gcd(n, mod)
    inv = table[1][1]
    if inv < 0:
        inv += mod
    return inv

def mod_pow(x, n, mod):
    ret = 1
    while n > 0:
        if n & 1 != 0:
            ret *= x
            ret %= mod
        x *= x
        x %= mod
        n >>= 1
    return ret

l = input().split()
Q = int(l[0])
X = []
D = []
N = []
for i in range(Q):
    l = input().split()
    X.append(int(l[0]))
    D.append(int(l[1]))
    N.append(int(l[2]))


for i in range(Q):
    x = X[i]
    d = D[i]
    n = N[i]
    if d == 0:
        print(mod_pow(x, n, mod))
        continue
    inv_d = mod_inv(d, mod)
    x_d = (x * inv_d) % mod
    # print(i, x, d, n, inv_d, x_d, x_d + n - 1)
    if x_d + n - 1 >= mod:
        print(0)
        continue
    ans1 = fac[x_d + n - 1]
    ans2 = fac[x_d - 1]
    # print(ans1, ans2)
    ans = ans1 * mod_inv(ans2, mod)
    ans %= mod
    d_n = mod_pow(d, n, mod)
    ans = ans * d_n
    ans %= mod
    print(ans)
### BUGGY CODE ###


n,m = map(int,input().split())

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

ans = set([i for i in range(n)])

for i in range(m):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    if h[a] <= h[b]:
        ans = ans - {a}
    if h[b] <= h[a]:
        ans = ans - {b}

print(len(ans))


### FIXED CODE ###



n,m = map(int,input().split())

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

# a = [0] * m
# b = [0] * m

ma = [0]*n


for i in range(m):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    ma[a] = max(ma[a],h[b])
    ma[b] = max(ma[b],h[a])

ans = 0    
for i in range(n):
    if h[i] > ma[i]:
        ans += 1
        

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

# import math
N, Q = map(int, input().split())
# line = list(map(int, input().split()))
# line = input()
S = input()
question = []
ans = []
for _ in range(Q):
    question.append(list(map(int, input().split())))

for i in range(Q):
    start = question[i][0] - 1
    end = question[i][1]
    count = 0
    for j in range(start,end-1):
        if S[j] == 'A' and S[j+1] == 'C':
            count += 1
    ans.append(count)

for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

# import math
N, Q = map(int, input().split())
# line = list(map(int, input().split()))
# line = input()
S = input()
question = []
ac = [0] * N
ans = []
count = 0
for _ in range(Q):
    question.append(list(map(int, input().split())))

for i in range(N):
    if S[i] == 'C' and S[i-1] == 'A':
        count += 1
        ac[i] = count
    else:
        ac[i] = count

# print(ac)

for i in range(Q):
    start = question[i][0] - 1
    end = question[i][1] - 1
    tmp = ac[end] - ac[start]
    ans.append(tmp)

for i in range(len(ans)):
    print(ans[i])