Harryxun/stf_run huggingface dataset:
H, W, K = [int(_) for _ in input().split()]
fib = [1, 1, 2, 3, 5 ,8, 13, 21]
dp = [[1] + [0] * (W - 1)]
for j in range(1, H + 1):
    dp.append([0] * W)
    for i in range(W):
        if i == 0:
            dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2]) % 1000000007
        elif i == W - 1:
            dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
        else:
            dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
print(dp[H][K - 1])

### FIXED CODE ###

H, W, K = [int(_) for _ in input().split()]
fib = [1, 1, 2, 3, 5 ,8, 13, 21]
dp = [[1] + [0] * (W - 1)]
if W == 1:
    print(1)
else:
    for j in range(1, H + 1):
        dp.append([0] * W)
        for i in range(W):
            if i == 0:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2]) % 1000000007
            elif i == W - 1:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
            else:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
    print(dp[H][K - 1])
import sys
sys.setrecursionlimit=10**12

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
        for x in neighbor[p]:
            if x==par[p]: continue
            try:
                par[x]=p
            except: print(0);sys.exit()
            descend[p]+=cur(x)
        return descend[p]


def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[1]+[0]*(n)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)
cur(1)

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

for i in range(1,n+1):
    print(ans[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
    if neighbor[p]==[]: return
    for x in neighbor[p]:
        par[x]=p
        neighbor[x].remove(p)
        cur(x)
    descend[par[p]]+=descend[p]

def cur2(p):
    for x in neighbor[p]:
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[set()  for _ in range(n+2)]
descend=[1 for i in range(n+1)]
par=[0]+[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].add(b)
    neighbor[b].add(a)

cur(1)


ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

for i in range(1,n+1):
    print(ans[i])
s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1 #初期値の設定
for i in range(l):
if s[i]=='?': #?のときは各値(0～9)について更新する
  for j in range(10):
    for k in range(13):
      dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
else:
  for k in range(13): #整数のときはその値について更新する
    dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
print(dp[-1][5]%mod) #最後まで更新を行ったときのあまりが5となる数の個数が答え

### FIXED CODE ###

S = input()
l = len(S)
dp = [[0] * 13 for _ in range(l+1)]
dp[0][0] = 1
MOD = 10 ** 9 + 7
mul = 1
for i in range(l):
    if S[-(i+1)] == '?':
        for j in range(10):
            for k in range(13):
                dp[i+1][(j * mul + k) % 13] += dp[i][k]
                dp[i+1][(j * mul + k) % 13] %= MOD
    else:
        j = int(S[-(i+1)])
        for k in range(13):
            dp[i+1][(j * mul + k) % 13] += dp[i][k]
            dp[i+1][(j * mul + k) % 13] %= MOD
    mul = mul * 10 % 13
print(dp[l][5])
lis2 = list(map(int, input().split()))
n = lis[0]
k = lis[1]
d = {}

for i in range(n):
    if lis2[i] not in d.keys():
       d[lis2[i]] = 1
    else:
        d[lis2[i]] += 1 
        
if len(b) <= k:
    print(0)
else:
    a = d.values()
    a.sort()
    a.reverse()
    swap = 0
    for i in range(k,len(a)):
        swap += a[i]
    print(swap)

### FIXED CODE ###

lis = list(map(int, input().split()))
lis2 = input().split()
n = lis[0]
k = lis[1]
d = {}

for i in range(n):
    if lis2[i] not in d.keys():
       d[lis2[i]] = 1
    else:
        d[lis2[i]] += 1 
        
if len(list(d.values())) <= k:
    print(0)
else:
    a = list(d.values())
    a.sort()
    a.reverse()
    swap = 0
    for i in range(k,len(a)):
        swap += a[i]
    print(swap)
mport math
from functools import reduce

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


N=int(input())
S=0
T=0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        for k in range(j+1,N+1):
            S+=gcd(i,j,k)
for i in range(1,N+1):
    for j in range(i+1,N+1):
            T+=gcd(i,j,j)
            T+=gcd(i,j,j)
print(6*S+3*T+N*(N+1)//2)

### FIXED CODE ###

import math
from functools import reduce

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


N=int(input())
S=0
T=0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        for k in range(j+1,N+1):
            S+=gcd(i,j,k)
for i in range(1,N+1):
    for j in range(i+1,N+1):
            T+=gcd(i,j,j)
            T+=gcd(i,j,j)
print(6*S+3*T+N*(N+1)//2)
x = int(input())
eps = 1e-9
a = 1
while a**5 <= x:
    diff = a**5-x
    if diff < 0:
        diff = abs(diff)
        sign = True
    else:
        sign = False
    if abs(diff**0.2 - round(diff**0.2)) < eps:
        b = round(round(diff**0.2))
        if sign:
            b = -b
        break
    a += 1
print a,int(b)


### FIXED CODE ###

import sys
input = sys.stdin.readline

x = int(input())
eps = 1e-9
a = 1
while True:
    diff = a**5-x
    if diff < 0:
        diff = abs(diff)
        sign = True
    else:
        sign = False
    if abs(diff**0.2 - round(diff**0.2)) < eps:
        b = round(diff**0.2)
        if sign:
            b = -b
        break
    a += 1
print a,int(b)
input = input().split()

n = s[0]
k = s[1]

if n ==1 :
    print(0)
else:
    print(n-k)

### FIXED CODE ###

s = input().split()

n = int(s[0])
k = int(s[1])

if k==1 :
    print(0)
else:
    print(n-k)
#https://atcoder.jp/contests/abc167/tasks/abc167_c C - Skill Up
import numpy as np
from itertools import combinations
N,M,X=list(map(int,input().split()))
book_dict={}
for i in range(M):
    book_dict[i] = list(map(int,input().split()))

answer = (10**5*12)+1
for i in range(M,0,-1):
    for v in combinations(book_dict.keys(), i):
        search_book = list(map(lambda x:book_dict[x],list(v)))
        sum_search_book = np.array(np.sum(search_book,axis = 0))
        if (np.count_nonzero(sum_search_book[1:] >= X) == N) and sum_search_book[0] < answer:
            answer = sum_search_book[0]
                                                                                 
    
if answer == (10**5*12)+1:
    answer = -1

print(answer)


### FIXED CODE ###

#https://atcoder.jp/contests/abc167/tasks/abc167_c C - Skill Up
import numpy as np
from itertools import combinations
N,M,X=list(map(int,input().split()))
book_dict={}
for i in range(N):
    book_dict[i] = list(map(int,input().split()))

answer = (10**5*12)+1
for i in range(N,0,-1):
    for v in combinations(book_dict.keys(), i):
        search_book = list(map(lambda x:book_dict[x],list(v)))
        sum_search_book = np.array(np.sum(search_book,axis = 0))
        if (np.count_nonzero(sum_search_book[1:] >= X) == M) and sum_search_book[0] < answer:
            answer = sum_search_book[0]
                                                                                 
    
if answer == (10**5*12)+1:
    answer = -1

print(answer)
a, b, c = map(int, raw_input().split(""))
if a < b and b < c:
 print "Yes"
else:
 print "No"

### FIXED CODE ###

a, b, c = map(int, raw_input().split())
if a < b and b < c:
 print "Yes"
else:
 print "No"
N, K =map(int, input().split())
snuke = [0]*N

for i in range(K):
    d = int(input())
    a = list(map(int,input().split()))
    for j in range(d):
        snuke[a[j]] = 1

print(snuke.count(0))

### FIXED CODE ###

N, K =map(int, input().split())
snuke = [0]*N

for i in range(K):
    d = int(input())
    a = list(map(int,input().split()))
    for j in range(d):
        snuke[a[j]-1] = 1

print(snuke.count(0))
ef ALDS1_3B():
    n, q = map(int, input().split())
    PQ = [[l[0], int(l[1])] for l in  [input().split() for i in range(n)]  ]
    times = 0
    while PQ:
        p = PQ.pop(0)
        if p[1] <= q:
            times += p[1]
            print('%s %d' %(p[0], times))
        else:
            times += q
            PQ.append([p[0], p[1]-q])


if __name__ == '__main__':
    ALDS1_3B()

### FIXED CODE ###

def ALDS1_3B():
    n, q = map(int, input().split())
    PQ = [[l[0], int(l[1])] for l in  [input().split() for i in range(n)]  ]
    times = 0
    while PQ:
        p = PQ.pop(0)
        if p[1] <= q:
            times += p[1]
            print('%s %d' %(p[0], times))
        else:
            times += q
            PQ.append([p[0], p[1]-q])


if __name__ == '__main__':
    ALDS1_3B()
a,b=map(int,input(),split())

if a < b:
    print("a<b")
else:
    if a == b:
        print("a=b")
    else:
        if a>b:
            print("a>b")

### FIXED CODE ###

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

if a < b:
    print("a < b")
else:
    if a ==b:
         print("a == b")
    else:
        if a>b:
            print( "a > b" )
import bisect
from collections import deque
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]



def main():
    N, X, M = read_values()
    F = [-1] * M

    A = X
    t = 0
    while F[A] < 0:
        F[A] = t
        A = pow(A, 2, M)
        t += 1
    
    if t == 1:
        print(X * N)
    else:
        d = (N - F[A]) // (t - F[A])
        r = (N - F[A]) % (t - F[A]) + F[A]

    K = 0
    for i in range(F[A], t):
        K += A
        A = pow(A, 2, M)
    
    K *= d

    A = X
    for _ in range(r):
        K += A
        A = pow(A, 2, M)

    print(K)


if __name__ == "__main__":
    main()



### FIXED CODE ###

import bisect
from collections import deque
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]



def main():
    N, X, M = read_values()
    F = [-1] * (M + 1)

    A = X
    t = 0
    while F[A] < 0:
        F[A] = t
        A = pow(A, 2, M)
        t += 1
    
    if t == 1:
        print(X * N)
        return
    d = (N - F[A]) // (t - F[A])
    r = ((N - F[A]) % (t - F[A])) + F[A]

    K = 0
    for _ in range(F[A], t):
        K += A
        A = pow(A, 2, M)
    
    K *= d

    A = X
    for _ in range(r):
        K += A
        A = pow(A, 2, M)

    print(K)


if __name__ == "__main__":
    main()
n,k=map(int,input().split())
a=list(map(str,input().split()))
a=[0]+a

s="0"
t=1
flag1=0
flag2=0
for i in range(1,n+1):
    if a[t] not in s:
        s+=a[t]
        t=int(a[t])
    else:
        flag1=s.find(a[t])
        flag2=i
        break

if flag1==0:print(s[(k-1)%n+1])
else:
    if k<=flag2-1-1+1:print(s[k])
    else:
        s='0'+s[flag1:flag2]  #上下保持一致，左边加上0
        #print(s)
        print(s[(k-(flag1-1))%(flag2-1-flag1+1)])  #去除非循环节部分后求余











### FIXED CODE ###

def LIST():return list(map(int,input().split()))
def MAP():return map(int,input().split())

n,k=MAP()
a=LIST()
a=[0]+a
s=[0]
loca=1
begin=end=0
temp=[-1]*(2*10**5+1)
for i in range(1,n+1):
    s.append(a[loca])
    loca=a[loca]
    if k==i:
        print(s[i])
        exit()
    if temp[loca]==-1:
        temp[loca]=i
    else:
        begin=temp[loca]
        end=i-1
        break

if begin==0:print(s[(k-1)%n+1])
else:
    k=k-(begin-1)
    s=[0]+s[begin:]
    print(s[(k-1)%(end-begin+1)+1])
inr = lambda: list(map(int, input().split()))

N, Y = inr()

lmn = [-1, -1, -1]

for x in range(N+1):
    for y in range(N+a):
        z = N - x - y
        oto_sum = 10000 * x + 5000 * y + 1000 * z
        if z > 0 and oto_sum == Y:
            lmn[0] = x
            lmn[1] = y
            lmn[2] = z

print(lmn[0], lmn[1], lmn[2])

### FIXED CODE ###

inr = lambda: list(map(int, input().split()))

N, Y = inr()

lmn = [-1, -1, -1]

for x in range(N+1):
    for y in range(N-x+1):
        z = N - x - y
        oto_sum = 10000 * x + 5000 * y + 1000 * z
        if z >= 0 and oto_sum == Y:
            print(x, y, z)
            exit()

print(-1, -1, -1)
n=int(input())
out = n.replace("1","a")
out = n.replace("9","1")
out = n.replace("a","9")
print(out)

### FIXED CODE ###

n = list(input())

for i in range(3):
    if n[i] == "1":
        n[i] = "9"
    elif n[i] == "9":
        n[i] = "1"

for j in range(3):
  print(n[j], end="")
n = int(input())
b = [*map(int, input().split())]

sum_a = b[0] + b[-1]
for i in range(1,n-1):
    sum_a += min(b[i],b[i-1])
print (sum_a)

### FIXED CODE ###

n = int(input())
b = list(map(int, input().split()))
a = [int(0) for i in range(n)]
a[0] = b[0]
a[n-1] = b[n-2]
b.append(b[n-2])
for i in range(1,n-1):
    a[i] = min(b[i-1], b[i])
print(sum(a))
N = int(input())
A = tuple(int(x) for x in input().split())
B = tuple(int(x) for x in input().split())
C = tuple(int(x) for x in input().split())

satisfy = sum(B)

for i in range(len(A)-1):
  if A[i+1]-A[i] is 1:
    satisfy += C[A[i]]

print(satisfy)

### FIXED CODE ###

N = int(input())
A = tuple(int(x) for x in input().split())
B = tuple(int(x) for x in input().split())
C = tuple(int(x) for x in input().split())

satisfy = sum(B)

for i in range(N-1):
  if A[i+1]-A[i] is 1:
    satisfy += C[A[i]-1]

print(satisfy)
if "##" in S[A-1:C]:
	print("No")
elif "##" in S[B-1:D]:
	print("No")
elif D < C:	# A jumps over B
	if not "..." in S[B-1:C]:
		print("No")
	elif S[B-1:D].count("...") < 2:
		if S[D-2:D+1] == "#..":
			print("No")
		else:
			print("Yes")
	else:
		print("Yes")
else:
	print("Yes")

### FIXED CODE ###

N, A, B, C, D = map(int, input().split())
S = input()	# .#

if "##" in S[A-1:C]:
	print("No")
elif "##" in S[B-1:D]:
	print("No")
elif D < C:	# A jumps over B
	if not "..." in S[B-2:D+1]:
		print("No")
	else:
		print("Yes")
else:
	print("Yes")
A, B, C, D = map(int, input().split())
print(max(A*B), max(C* D))

### FIXED CODE ###

A, B, C, D = map(int, input().split())
print(max(A*B, C* D))
strlist = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y"]
print(strlist[strlist.index(input()) + 1])

### FIXED CODE ###

strlist = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
print(strlist[strlist.index(input()) + 1])
a,b,c=map(int,input().split())
d=a-b
if c-d=>0:
  print(c-d)
else:
  print(0)
    

### FIXED CODE ###

a,b,c=map(int,input().split())
d=a-b
e=c-d
if e>=0:
  print(e)
else:
  print(0)
n = int(input())

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

mod = 10**9 + 7

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

x = lcm_list(a)
# print(x)

ans = 0
for i in range(n):
    ans += int(x/a[i])%mod

print(int(ans)%mod)

### FIXED CODE ###

n = int(input())

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

mod = 10**9 + 7

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

x = lcm_list(a)
# print(x)

ans = 0
for i in range(n):
    ans += int(x//a[i])

print(int(ans)%mod)
import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = rl()
color = [0] * 3
answer = 1
MOD = 10 ** 9 + 7

for a in A:
    answer *= color.count(a)
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

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

color = [0] * 3 # 赤色・青色・緑色の帽子を被っている人数
answer = 1 
MOD = 10 ** 9 + 7

for a in A:
    if color.count(a) == 0:
        print(0)
        exit()
    answer *= color.count(a)
    # aと同じ人数が複数ある場合は一番左の色としてカウント
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)
n=int(input())
d=list(map(int,input().split()))
D=sorted(d)
print(D[(n/2)]-D[(n/2)-1])


### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
D=sorted(d)
num=D[n//2]-D[(n//2)-1]
print(num)
n,x=map(int,input().split())
a=list(int(input()) for _ range(n))
print(n+(x-sum(a))//min(a))

### FIXED CODE ###

n,x=map(int,input().split())
a=list(int(input()) for _ in range(n))
print(n+((x-sum(a))//min(a)))
N=int(input())
lamps=[]
for a in range(N):
    _=int(input())
    lamps.append(_)
lamps.insert(0,"aaa")

PressedButtons=[False]*N

a=1
count=0


while True:
    if PressedButtons[a]==False:
        PressedButtons[a]=True
        count+=1
        a=lamps[a]
        if a==2:
            print(count)
            exit()
    elif PressedButtons[a]==True:
        print("-1")
        exit()
    else:
        print("-1")

### FIXED CODE ###

N=int(input())
lamps=[]
for a in range(N):
    _=int(input())
    lamps.append(_)
lamps.insert(0,"aaa")

PressedButtons=[False]*int(N+1)

a=1
count=0

if lamps.count(2)==0:
    print("-1")
    exit()

while PressedButtons[a]==False :
    PressedButtons[a]=True
    count+=1
    a=lamps[a]
    if a==2:
        print(count)
        exit()
print('-1')
N ,D = map(int, input().split())
X = []
tmp = []
ans = []
for _ in range(N):
    X.append(list(map(int, input().split())))
for i in range(N):
    for j in range(D):
        tmp.append((X[i-1][j]-X[i][j])**2)
    ans.append(tmp[0] + tmp[1])
print(ans)

### FIXED CODE ###

N ,D = map(int, input().split())
X = []
tmp = []
ans = []
fans = 0
for _ in range(N):
    X.append(list(map(int, input().split())))
for i in range(N-1):
    for j in range(i+1, N):
        if D == 1:
            tmp.append((X[i][0]-X[j][0])**2)
        else:
            for k in range(D):
                tmp.append((X[i][k]-X[j][k])**2)
        ans.append(sum(tmp)**0.5)
        tmp = []
for A in ans:
    if A.is_integer():
        fans += 1
print(fans)
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

#from fractions import Fraction
from math import gcd

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a == 0:
        if b != 0:
            azero += 1
        else:
            allzero += 1
    elif b == 0:
        bzero += 1            
    else:
        '''
        ratio = Fraction(a,b)
        before = cnd.get(ratio,False)
        if before:
            cnd[ratio] = [before[0]+1,before[1]]
        else:
            invratio = Fraction(-b,a)
            check = cnd.get(invratio,False)
            if check:
                cnd[invratio] = [check[0],check[1]+1]
            else:
                cnd[ratio] = [1,0]
        '''
        g = gcd(a,b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        cnd[(a,b)] += cnd.get((a,b),0)


noreg = 0
if azero == 0 or bzero == 0:
    noreg += max(azero,bzero)
else:
    ans = (2**azero%mod + 2**bzero%mod - 1)%mod

for k,item in cnd:
    a,b = k
    if b>0:
        m = cnd.get((-b,a),False)
        if m:
            ans *= (2**item%mod+2**m%mod-1)%mod
        else:
            noreg += item
    else:
        m = cnd.get((-b,a),False)
        if not m:
            noreg += item
#print('hoge')
print(int((ans*((2**noreg)%mod)-1+allzero)%mod))

### FIXED CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

#from fractions import Fraction
from math import gcd

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a == 0:
        if b != 0:
            azero += 1
        else:
            allzero += 1
    elif b == 0:
        bzero += 1            
    else:
        '''
        ratio = Fraction(a,b)
        before = cnd.get(ratio,False)
        if before:
            cnd[ratio] = [before[0]+1,before[1]]
        else:
            invratio = Fraction(-b,a)
            check = cnd.get(invratio,False)
            if check:
                cnd[invratio] = [check[0],check[1]+1]
            else:
                cnd[ratio] = [1,0]
        '''
        g = gcd(a,b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        cnd[(a,b)] = cnd.get((a,b),0)+1


noreg = 0
if azero == 0 or bzero == 0:
    noreg += max(azero,bzero)
    ans = 1
else:
    ans = (2**azero%mod + 2**bzero%mod - 1)%mod
#print('ans block')
#print(ans,noreg)
#print(cnd)
for k,item in cnd.items():
    a,b = k
    if b>0:
        m = cnd.get((b,-a),False)
        if m:
            ans *= (2**item%mod+2**m%mod-1)%mod
        else:
            noreg += item
    else:
        m = cnd.get((-b,a),False)
        if not m:
            noreg += item
#print('hoge')
print(int((ans*((2**noreg)%mod)-1+allzero)%mod))
a = ""
b = list(map(int, input().split()))
for i in range(3):
  a += b[i]
if int(a)%4:
  print("NO")
else:
  print("YES")

### FIXED CODE ###

a = ""
b = list(map(int, input().split()))
for i in range(3):
  a += str(b[i])
if int(a)%4:
  print("NO")
else:
  print("YES")
import math

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]

for x in range(min(k,math.log(n, 10))):
    new_a = [0]*n
    for j,l in enumerate(a):
        for i in range(-l,l+1):
            if j+i >= 0 and j+i<n:
                new_a[j+i]+=1
    a = new_a

print(" ".join([str(x) for x in a]))

### FIXED CODE ###

import math
import numpy as np

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]


for _ in range(k):
    new_a = np.zeros(n+1,dtype=int)
    np.add.at(new_a, np.maximum(0,np.arange(0, n)-a), 1)
    np.add.at(new_a, np.minimum(n,np.arange(0, n)+a+1), -1)
    a = new_a.cumsum()[:-1]
    if np.all(a==n):
        break

print(" ".join([str(x) for x in a]))
import numpy as np
from math import gcd
from functools import reduce
def LGcd(l):
    return reduce(gcd,l)
N, X = map(int,input().split())
k = np.array(input().split())
k = k.astype(np.int32)
k -= X
if N == 1:
    print(str(abs(k[0])))
else:
    print(str(LGcd(k)))

### FIXED CODE ###

# 正の数を受け取るように定義
def gcd(a,b):
    if b == 0:
        return a 
    return gcd(b,a % b)

N, X = map(int,input().split())
k = [abs(int(x) - X) for x in input().split()] # リスト内包表記で入力の受け取り
a = k[0]
for i in range(1,N):
    a = gcd(a,k[i])
print(str(a))