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

N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
LR.sort()
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    f = 0
    if ma[i] != 0:
        for l,r in LR:
            for j in range(l,r+1):
                if i+j < N:
                    ma[i+j] += ma[i]
                else:
                    f = 1
                    break
            if f:
                break
print(ma[N-1]%mod)

### FIXED CODE ###

N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
LR.sort()
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if i >1:
        ma[i] += ma[i-1]
    p = ma[i]%mod
    if p != 0:
        for l,r in LR:
            if i+l <N:
                ma[i+l] += p
            else:
                break
            if i+r+1<N:
                ma[i+r+1] -= p
print(ma[N-1]%mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import math

N, M, K = [int(item) for item in input().split()]
mod = 10**9 + 7

total = 0
for d in range(1, N):
    score = (N - d) * M**2 * d
    score %= mod
    for i in range(2, K):
        score *= ((N * M - i) % mod * pow(K - i, mod - 2, mod))
        score %= mod
    total += score
    total %= mod

for d in range(1, M):
    score = (M - d) * N**2 * d
    score %= mod
    for i in range(2, K):
        score *= ((N * M - i) % mod * pow(K - i, mod - 2, mod))
        score %= mod
    total += score
    total %= mod


print(total)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import math

N, M, K = [int(item) for item in input().split()]
mod = 10**9 + 7

score_c = 1
for i in range(2, K):
    score_c *= ((N * M - i) % mod * pow(K - i, mod - 2, mod))
    score_c %= mod

total = 0
for d in range(1, N):
    score = (N - d) * M**2 * d * score_c
    score %= mod
    total += score
    total %= mod

for d in range(1, M):
    score = (M - d) * N**2 * d * score_c
    score %= mod
    total += score
    total %= mod


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

h,w=map(int,input().split())
a=[[int(i) for i in input().split()] for i in range(h)]
b=[[int(i) for i in input().split()] for i in range(h)]
for i in range(h):
    if i==0:
        x=[set([]) for _ in range(w)]
    for j in range(w):
        if i==0 and j==0:
            x[0].add(abs(a[0][0]-b[0][0]))
        elif i==0 and j!=0:
            for k in x[j-1]:
                x[j].add(abs(k+(a[i][j]-b[i][j])))
                x[j].add(abs(k+(b[i][j]-a[i][j])))
        elif i%2:
            if j==0:
                for k in x[0]:
                    y[j].add(abs(k+(a[i][j]-b[i][j])))
                    y[j].add(abs(k+(b[i][j]-a[i][j])))
            else:
                for k in x[j]:
                    y[j].add(abs(k+(a[i][j]-b[i][j])))
                    y[j].add(abs(k+(b[i][j]-a[i][j])))
                for k in y[j-1]:
                    y[j].add(abs(k+(a[i][j]-b[i][j])))
                    y[j].add(abs(k+(b[i][j]-a[i][j])))
        else:
            if j==0:
                for k in y[0]:
                    x[j].add(abs(k+(a[i][j]-b[i][j])))
                    x[j].add(abs(k+(b[i][j]-a[i][j])))
            else:
                for k in y[j]:
                    x[j].add(abs(k+(a[i][j]-b[i][j])))
                    x[j].add(abs(k+(b[i][j]-a[i][j])))
                for k in x[j-1]:
                    x[j].add(abs(k+(a[i][j]-b[i][j])))
                    x[j].add(abs(k+(b[i][j]-a[i][j])))

    if i%2==0:
        y=[set([]) for _ in range(w)]
        ans=min(x[-1])
    else:
        x=[set([]) for _ in range(w)]
        ans=min(y[-1])
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
H,W = map(int,readline().split())
A = [list(map(int,readline().split())) for _ in range(H)]
B = [list(map(int,readline().split())) for _ in range(H)]
 
X = (H + W) * 80
# X点持った状態から始める
dp = [[0] * W for _ in range(H)]
d = abs(A[0][0] - B[0][0])
dp[0][0] = (1 << (X - d))
for h in range(H):
    for w,(a,b) in enumerate(zip(A[h],B[h])):
        if h == w == 0:
            continue
        d = abs(a - b)
        x = 0
        if h != 0:
            x |= (dp[h-1][w] << d) 
            x |= (dp[h-1][w] >> d)
        if w != 0:
            x |= (dp[h][w-1] << d) 
            x |= (dp[h][w-1] >> d)
        dp[h][w] = x
 
dp = dp[-1][-1]
 
B = bin(dp)[2:]
can_make = [i - X for i,b in enumerate(B[::-1]) if b == '1']
 
answer = min(x if x >= 0 else -x for x in can_make)
print(answer)
### BUGGY CODE ###

import bisect

n = int(input())
A = []
count = 0
for _ in range(n):
    a = int(input())
    if len(A) == 0:
        A.append(a)
        count += 1
        continue
    i = bisect.bisect_left(A, a)
    if i == 0:
        A.insert(0, a)
        count += 1
    else:
        A[i-1] = a

ans = count
print(ans)

### FIXED CODE ###

import bisect
from collections import deque

n = int(input())
A = []
dq_A = deque(A)
count = 0
for _ in range(n):
    a = int(input())
    if len(dq_A) == 0:
        dq_A.appendleft(a)
        count += 1
        continue
    i = bisect.bisect_left(dq_A, a)
    if i == 0:
        dq_A.appendleft(a)
        count += 1
    else:
        dq_A[i-1] = a

ans = count
print(ans)
### BUGGY CODE ###

def gcd(p, q):
    if p%q == 0:
        return q
    else:
        return gcd(q, p%q)

k = int(input())
s = 0

for h in range(1, k+1):
    for i in range(1, k+1):
        for j in range(1, k+1):
            s += gcd(gcd(h, i), j)

print(s)

### FIXED CODE ###

from functools import reduce
import math

k = int(input())

s = 0

def gcd(*numbers):
    return reduce(math.gcd, numbers)

for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            s += gcd(i,j,l)

print(s)
### BUGGY CODE ###

s=list(input())
n=len(s)+1
a=[0]*n
x=[0]*n
y=[0]*n

for i in range(0,n):
  c=i
  while i>0 and s[i-1]=="<":
    x[c]+=1
    i-=1
for j in range(0,n):
  d=j
  while j<n-1 and s[j]==">":
    y[d]+=1
    j+=1

for k in range(0,n):
  a[k]=max(x[k],y[k])
  
print(sum(a))  
    
    
  
  


### FIXED CODE ###

s=list(input())
n=len(s)+1
a=[0]*n
x=[0]*n
y=[0]*n

for i in range(1,n):
  if s[i-1]=="<":
    x[i]=x[i-1]+1
  else:
    x[i]=0
    
for j in range(n-2,-1,-1):
  if s[j]==">":
    y[j]=y[j+1]+1
  else:
    y[j]=0

for k in range(0,n):
  a[k]=max(x[k],y[k])
  
print(sum(a))
### BUGGY CODE ###

s = input()
q = int(input())
T = [0]*q
F = [0]*q
C = ['' for i in range(q)]

for i in range(q):
    x = input()
    if x[0]==str(1):
        T[i]=1
    else:
        t,f,c = x.split()
        T[i],F[i],C[i] = int(t),int(f),c

tmp = 1
for i in range(q):
    if T[i]==1:
        tmp*=-1
    if T[i]==2:
        if tmp==-1:
            if F[i]==1:
                s = s+C[i]
            if F[i]==2:
                s = C[i]+s
        if tmp==1:
            if F[i]==1:
                s = C[i]+s
            if F[i]==2:
                s = s+C[i]

print(s[::tmp])

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
queue = deque([s])

tmp = 1
for i in range(q):
    x = input()
    if x[0]==str(1):
        tmp*=-1
    else:
        t,f,c = x.split()
        t,f = int(t),int(f)
        if tmp==-1:
            if f==1:
                queue.append(c)
            if f==2:
                queue.appendleft(c)
        if tmp==1:
            if f==1:
                queue.appendleft(c)
            if f==2:
                queue.append(c)

print(''.join(queue)[::tmp])
### BUGGY CODE ###

S=str(input())
Q=int(input())
which=0
front=[]
back=[]
for i in range(Q):
    a=list(map(str,input().split()))
    if a==["1"]:
        which+=1
        which%=2
        continue
    else:
        if which==0:
            if a[1]=="1":
                front.insert(0,a[2])
            if a[1]=="2":
                back.append(a[2])
        if which==1:
            if a[1]=="1":
                back.append(a[2])
            if a[1]=="2":
                front.insert(0,a[2])
F="".join(front)
B="".join(back)
S=F+S+B
if which==1:
    print("".join(S[len(S)-i-1] for i in range(len(S))))
if which==0:
    print(S)


### FIXED CODE ###

S=str(input())
Q=int(input())
which=0
front=""
back=""
for i in range(Q):
    a=list(map(str,input().split()))
    if a==["1"]:
        which+=1
        which%=2
        continue
    else:
        if which==0:
            if a[1]=="1":
                front=a[2]+front
            if a[1]=="2":
                back+=a[2]
        if which==1:
            if a[1]=="1":
                back+=a[2]
            if a[1]=="2":
                front=a[2]+front

S=front+S+back
if which==1:
    print(S[::-1])
if which==0:
    print(S)
### BUGGY CODE ###

#通るかな？
def 解():
    import sys
    input = sys.stdin.readline

    N,Q = [int(_) for _ in input().split()]

    S = input()
    dS = {}
    for i in range(1,N+1):
        s = S[i-1]
        if s in dS:
            dS[s].add(i)
        else:
            dS[s] = {i}
    #aM = [1]*(N+2)
    aM = {i:1 for i in range(N+2)}

    for _ in range(Q):
        t,d = input().split()
        if t in dS:
            if d == "R":
                for i in dS[t]:
                    if aM[i]:
                        aM[i+1] += aM[i]
                        aM[i] = 0
            else:
                for i in dS[t]:
                    if aM[i]:
                        aM[i-1] += aM[i]
                        aM[i] = 0

    print(sum(aM[i] for i in range(1,N+1)))
解()


### FIXED CODE ###

#こうけ？
def 解():
    import sys
    input = sys.stdin.readline
    N,Q = [int(_) for _ in input().split()]
    S = " " + input() + " "
    aC = [[ _.rstrip() for _ in  _.split()] for _ in sys.stdin.readlines()]
    iL = 0
    iR = N+1
    for t,d in aC[::-1]:
        if t == S[iL+1] and d == "L" and iL < N+1:
                iL += 1
        elif t == S[iL] and d == "R" and 0 < iL:
                iL -= 1

        if t == S[iR-1] and d == "R" and 0 < iR:
                iR -= 1
        elif t == S[iR] and d == "L" and  iR < N+1:
                iR += 1
    if iL < iR:
        print(iR-iL-1)
    else:
        print(0)
解()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = map(int,input().split())
data = [0] * (k+1)
for i in range(k,0,-1):
  tmp =  (k//i) ** n
  for j in range(i+i,k+1,i):
    tmp -= data[j]
  data[i] = tmp % mod
ans = 0
for i,di in enumerate(data):
  ans += i * di
  ans %= mod
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = map(int,input().split())
data = [0] * (k+1)
for i in range(k,0,-1):
  tmp = pow(k//i,n,mod)
  for j in range(i+i,k+1,i):
    tmp -= data[j]
  data[i] = tmp % mod
ans = 0
for i,di in enumerate(data):
  ans += i * di
  ans %= mod
print(ans)
# print(data)
### BUGGY CODE ###

n = int(input())
mlist = []
for i in range(n):
    m = int(input())
    mlist.append(m)
mlist.sort()
plist = [2]
for i in range(3,mlist[-1]+1):
    count = 0
    for k in plist:
        if (i%k != 0):
            count += 1
        else:
            break
    if (count == len(plist)):
        plist.append(i)
count = 0
for i in mlist:
    if(i in plist):
        count += 1
print(count)  



### FIXED CODE ###

n = int(input())
mlist = []
plist = [2]
for i in range(3,10000):
    count = 0
    for k in plist:
        if (i%k != 0):
            count += 1
        else:
            break
    if (count == len(plist)):
        plist.append(i)
def check(m):
    for p in plist:
        if (m <= p):
            return True
        if m%p == 0:
            return False     ##한번이라도 False가 return되면 False가 되기에 prime인지 아닌지 check가능
    return True

count = 0
for i in range(n):
    m = int(input())
    if check(m):
        count += 1
        
print(count)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def main():
    # n, m = map(int, input().split())
    # a = [int(input()) for i in range(m)]
    n, m = map(int, readline().split())
    a = list(map(int, read().split()))
    mod = 1000000007

    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # 2回0が続く状況aに連番があったら即座に終了する
    cnt = 0 
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def main():
    # n, m = map(int, input().split())
    # a = [int(input()) for i in range(m)]
    n, m = map(int, readline().split())
    a = set(map(int, read().split()))
    mod = 1000000007

    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # 2回0が続く状況aに連番があったら即座に終了する
    cnt = 0 
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)

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

def popcount(x):
    return bin(x).count("1")

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)
cache = {}

for i in range(0, N):
    x = X
    x = x ^ (1 << (N - 1 - i))
    x_ = x
    ans = 0
    while x != 0:
        if x in cache:
            ans += cache[x]
            break
        y = popcount(x)
        x = x % y
        ans += 1
    cache[x_] = ans
    print(ans)

### FIXED CODE ###

def popcount(x):
    return bin(x).count("1")

N, X = open(0).read().split()
N = int(N)
XS = list(X)
X = int(X, 2)

p = popcount(X)
xi = X % (p + 1)
if p == 1:
    xd = 0
else:
    xd = X % (p - 1)

for i in range(N):
    if XS[i] == "1":
        if p == 1:
            print(0)
            continue
        else:
            k = pow(2, N - 1 - i, p - 1)
            x = (xd - k) % (p - 1)
    else:
        k = pow(2, N - 1 - i, p + 1)
        x = (xi + k) % (p + 1)
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)
### BUGGY CODE ###

a, b, c, d = map(int, input().split(" "))
i = 1
while a != 0 and c != 0:
    if i % 2 == 1:
        c -= b
    else:
        a -= d
    i = 0 if i == 1 else 1

if a <= 0:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

a, b, c, d = map(int, input().split(" "))
i = 1
while a > 0 and c > 0:
    if i % 2 == 1:
        c -= b
    else:
        a -= d
    i = 0 if i == 1 else 1

if a <= 0:
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

N = int(input())
d = {}
for i in range(N):
    S = input()
    if S in d.keys():
        d[S] += 1
    else:
        d[S] = 1
key_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
for k in sorted(key_list):
    print(k)

### FIXED CODE ###

N = int(input())
d = {}
for i in range(N):
    S = input()
    if S in d.keys():
        d[S] += 1
    else:
        d[S] = 1
max_val = max(d.values())
key_list = [kv[0] for kv in d.items() if kv[1] == max_val]
for k in sorted(key_list):
    print(k)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for _ in range(q):
    l, r = map(int, input().split())
    print(s[l-1:r].count('AC'))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2]=='AC' else 0)
for i in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

S = input()
N = len(S)

S_inv = S[::-1]
mod = 10**9 +7
dp = [[0] * 13 for i in range(10**6)]

dp[0][0] = 1
for i,s in enumerate(S_inv):
    keta = i%6
    if s != "?":
        for j in range(13):
            amari = (j + int(s)*10**keta)%13 #桁を追加
            dp[i+1][amari] += dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                amari = (j + k*10**keta)%13
                dp[i+1][amari] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= mod
print(dp[N][5]%mod)

### FIXED CODE ###

S = input()
N = len(S)

mod = 10**9 +7
dp = [[0] * 13 for i in range(10**6)]

dp[0][0] = 1
for i,s in enumerate(S):
    keta = (N-i-1)%6
    if s != "?":
        for j in range(13):
            amari = (j + int(s)*10**keta)%13 #桁を追加
            dp[i+1][amari] += dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                amari = (j + k*10**keta)%13
                dp[i+1][amari] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= mod
print(dp[N][5]%mod)
### BUGGY CODE ###

N = int(input())
alist = []
for _ in range(N):
    alist.append(int(input()))
history = []
i = 1
while True:
    if i in history:
        print(-1)
        break
    history.append(i)
    i = alist[i - 1]
    if i == 2:
        print(len(history))
        break

### FIXED CODE ###

N = int(input())
alist = []
for _ in range(N):
    alist.append(int(input()))
i = 1
for n in range(N):
    i = alist[i - 1]
    if i == 2:
        print(n + 1)
        break
else:
    print(-1)
### BUGGY CODE ###

from math import sqrt
q = int(input())
l, r = [], []
for i in range(q):
    a, b = map(int, input().split())
    l.append(a)
    r.append(b)


like = [0] * 100001
prime = set()


def isprime(n):
    global prime
    if (n in prime):
        return True
    else:
        f = False
        for i in range(2, int(sqrt(n)) + 1):
            f |= (n % i == 0)

        if not f:
            prime.add(n)
        return not f


def is2017like(n):
    if n % 2 == 0:
        return False
    return isprime(n) & isprime((n + 1) // 2)


for i in range(1, 100001):
    like[i] = like[i-1] + int(is2017like(i))


for i in range(q):
    print(like[r[i]]-like[max(1, l[i]-1)])


### FIXED CODE ###

from math import sqrt
q = int(input())
l, r = [], []
for i in range(q):
    a, b = map(int, input().split())
    l.append(a)
    r.append(b)


like = [0] * 100001
prime = set()


def isprime(n):
    global prime
    if (n in prime):
        return True
    else:
        f = False
        for i in range(2, int(sqrt(n)) + 1):
            f |= (n % i == 0)

        if not f:
            prime.add(n)
        return not f


def is2017like(n):
    if n % 2 == 0:
        return False
    return isprime(n) & isprime((n + 1) // 2)


for i in range(1, 100001):
    like[i] = like[i-1] + int(is2017like(i))


for i in range(q):
    print(like[r[i]]-like[max(1, l[i]-1)])
### BUGGY CODE ###

n = int(input())
a_list = [0]
for _ in range(n):
    a_list.append(int(input()))
counter = 0
current_number = 1
already_pushed_list = []

while(True):
    counter += 1
    already_pushed_list.append(current_number)
    current_number = a_list[current_number]
    if current_number in already_pushed_list:
        print(-1)
        break
    if current_number == 2:
        print(counter)
        break


### FIXED CODE ###

n = int(input())
a_list = [0]
for _ in range(n):
    a_list.append(int(input()))
counter = 0
current_number = 1
already_pushed_list = set()

while(True):
    counter += 1
    already_pushed_list.add(current_number)
    current_number = a_list[current_number]
    if current_number in already_pushed_list:
        print(-1)
        break
    if current_number == 2:
        print(counter)
        break
### BUGGY CODE ###

N, Q = map(int, input().split())
S = str(input())
SD = {}

for n in range(N):
    SD[n] = S[n]

for q in range(Q):
    l, r = map(int, input().split())
    cnt = 0
    for i in range(l-1, r-1):
        if SD[i] + SD[i + 1] == "AC":
            cnt += 1
    print(cnt)

### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
SD = {}

cnt = 0
for n in range(1, N):
    if S[n-1] + S[n] == "AC":
        cnt += 1
    SD[n] = cnt

for q in range(1, Q+1):
    l, r = map(int, input().split())
    print(SD.get(r-1, 0)-SD.get(l-1, 0))
### BUGGY CODE ###

# E
s = list(input())
N = len(s)
res = True
if s[0] == "0" or s[N-1] == "1":
    res = False
for i in range(N-1):
    if s[i] != s[N-2-i]:
        res = False
if res == False:
    print(-1)
else:
    k = 1
    for i in range(N-1):
        if s[i] == "1":
            while k < i+1:
                print(str(k)+" "+str(i+1))
                k += 1
        while k < N:
            print(str(k)+" "+str(N))

### FIXED CODE ###

# E
s = list(input())
N = len(s)
res = True
if s[0] == "0" or s[N-1] == "1":
    res = False
for i in range(N-1):
    if s[i] != s[N-2-i]:
        res = False
if res == False:
    print(-1)
else:
    k = 1
    for i in range(N-1):
        if s[i] == "1":
            while k < i+1:
                print(str(k)+" "+str(i+1))
                k += 1
    while k < N:
        print(str(k)+" "+str(N))
        k += 1
### BUGGY CODE ###

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

a = [i for i in range(A,B+1)]

b = sorted(set(a[:K]+a[-K:]))

print(*b, sep = "\n")

### FIXED CODE ###

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

if K >= B:
  print(*sorted(range(A,B+1)), sep = "\n")

else:
  a = [i for i in range(A,min(B+1,A+K))]
  b = [i for i in range(B,max(A-1,B-K),-1)]
  print(*sorted(set(a+b)), sep = "\n")
### BUGGY CODE ###

Q = int(input())

a = [[int(i) for i in input().split()] for j in range(Q)]

for i in range(Q):
    m = a[i][0]
    for j in range(a[i][2]-1):
        m *= (a[i][0]+(j+1)*a[i][1])
    print(m%1000003)


### FIXED CODE ###

MOD = 10**6+3

def main():
    # preprocess
    fac = [1, 1]
    f_inv = [1, 1]
    inv = [0, 1]

    for i in range(2, MOD+1):
        fac.append((fac[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        f_inv.append((f_inv[-1] * inv[-1]) % MOD)

    Q = int(input())
    for i in range(Q):
        x, d, n = map(int, input().split())

        if d == 0:
            print(pow(x, n, MOD))
            continue
        
        xd = (x * pow(d, MOD-2, MOD)) % MOD
        if xd == 0 or xd + (n-1) >= MOD:
            print(0)
            continue

        print(pow(d, n, MOD) * fac[xd+(n-1)] * f_inv[xd-1] % MOD)


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

x,y=map(int,input().split());i=2
if x==y:
  print(-1)
else:
  while True:
    r=x*i
    if r%y!=0:
      print(r)
      break
    elif r>=(10**18):
      print(-1)
      break
    i+=1
    

### FIXED CODE ###

x, y=map(int, input().split())
print(-1 if x%y==0 else x)
### BUGGY CODE ###

F=lambda X:pow(X,M-2,M);M=10**9+7;H,W,A,B=map(int,input().split());Z=C=1
for I in range(min(W-1-B,H-1)):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*(H-I)*F(I)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)

### FIXED CODE ###

F=lambda X:pow(X,M-2,M);M=10**9+7;H,W,A,B=map(int,input().split());Z=C=1
for I in range(min(W-1-B,H-1)):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*F(I)*(H-I)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)