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

n, p = map(int, input().split())
s = input()

mod = (10 ** 9 + 7) ** 5 # (modの値をすごく大きくすれば（5乗とか）、普通のnCrとして使える)
MAX = 10 ** 5 + 1 # これは変動するので注意

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n, r):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    # dp = [0] * p
    # dp[0] = 1
    # tmp = 0
    # for i in range(n)[::-1]:
    #     tmp = (int(s[i]) * pow(10, n - i - 1, p) + tmp) % p
    #     print(tmp)
    #     ans += dp[tmp]
    #     dp[tmp] += 1
    # print(dp)

    # ベースの考え方。https://drken1215.hatenablog.com/entry/2020/03/08/020200
    # 素数pで割ったあまりは、0, 1, 2, ... p - 1になる。
    # 例えば、s=152467, p=3とする
    # 0 mod 3 = 0 (単独でも1つになるので、便宜上加える)
    # 7 mod 3 = 1
    # 67 mod 3 = 1
    # 467 mod 3 = 2
    # 2467 mod 3 = 1
    # 52467 mod 3 = 0
    # 152467 mod 3 = 1
    # となる。
    # 例えば、x mod 3 = 1について、考える。これは、7, 67, 2467, 152467の4つある。
    # これから、67 - 7 = 60で、3で割り切れる。2467 - 7 = 2560で、3で割り切れる。
    # このように、4つのうち2つを組み合わせれば、あまりの数が同じなので、p(3)で割り切れる組み合わせ
    # を作ることができる。
    # 467 mod 3 = 2については、あまりが2はコレしかないので、組み合わせることはできず、0となる。
    # また、あまりが2のものと、あまりが1のもの2個で組み合わせることはできない。なぜなら、
    # 467-67-7で組み合わせたところで、67と7が互いに相殺してしまうし、結果も393という、sの中に存在しない文字になるからである。
    # 基本はこれであり、下記のようになるが、これでは遅い。
    dp = [0] * p
    dp[0] = 1
    tmp = 0
    for i in range(n)[::-1]:
        tmp = (int(s[i:])) % p
        dp[tmp] += 1
    # print(dp)
    for i in dp:
        ans += nCr(i, 2)

print(ans)

### FIXED CODE ###

from collections import defaultdict
n, p = map(int, input().split())

s = input()
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    tmp = 0
    d = defaultdict(int)
    d[0] = 1
    for i in range(n)[::-1]:
        tmp += int(s[i]) * pow(10, n - i - 1, p)
        tmp %= p
        ans += d[tmp]
        d[tmp] += 1
print(ans)
### BUGGY CODE ###

n = int(input())
initial_vals = list(map(int, input().split(" ")))


table = [[None for x in range(n)] for x in range(n)]

for i in range(n - 1):
    table[i][i + 1] = abs(initial_vals[i] - initial_vals[i + 1])
    if len(initial_vals) > i + 2:
        table[i][i + 2] = abs(initial_vals[i] - initial_vals[i + 2])


def calc(from_stone, to_stone):
    if (to_stone - from_stone) == 1:
        return table[from_stone][to_stone]
    elif (to_stone - from_stone) == 2:
        return min(
            table[from_stone][to_stone],
            table[from_stone][to_stone - 1] + table[to_stone - 1][to_stone],
        )
    else:
        table[from_stone][to_stone] = min(
            calc(from_stone, to_stone - 1) + table[to_stone - 1][to_stone],
            calc(from_stone, to_stone - 2) + table[to_stone - 2][to_stone],
        )
        return table[from_stone][to_stone]


print(calc(0, n - 1))


### FIXED CODE ###

n = int(input())
initial_vals = list(map(int, input().split(" ")))


# print(calc(0, n - 1))


arr = [0 for x in range(n)]

arr[1] = abs(initial_vals[0] - initial_vals[1])

for i in range(2, len(arr)):
    arr[i] = min(
        arr[i - 1] + abs(initial_vals[i - 1] - initial_vals[i]),
        arr[i - 2] + abs(initial_vals[i - 2] - initial_vals[i]),
    )

print(arr[n - 1])
### BUGGY CODE ###

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

a = sorted(a)

for i in range(q):
    flag = 0
    for j in range(len(a)):
        if a[j] == bc[i][0]:
            a[j] = bc[i][1]
            flag += 1
        elif flag > 1:
            break

        # print(a)
    
    print(sum(a))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]

cnt = [0 for i in range(0, 10**5 + 1)]
for i in a:
    cnt[i] += 1

total = sum(a)

for j in range(q):
    b = bc[j][0]
    c = bc[j][1]
    cnt[c] += cnt[b]
    total += (c-b)*cnt[b]
    cnt[b] = 0
    print(total)
### BUGGY CODE ###

n,k=map(int,input().split())
A=list(map(int,input().split()))
F=list(map(int,input().split()))
A.sort(reverse=True)
F.sort()
ng=-1
ok=10**12
while ok-ng>1:
    mid=(ok+ng)//2
    temp=0
    flag=0
    for i in range(n):
        a=mid//F[i]
        if a>A[i]:
            continue
        else:
            temp+=A[i]-a
    if temp>k:
        flag=1
    if flag:
        ng=mid
    else:
        ok=mid

print(ok)

### FIXED CODE ###

n,k=map(int,input().split())
A=list(map(int,input().split()))
F=list(map(int,input().split()))
A.sort(reverse=True)
F.sort()
ng=-1
ok=10**12
while ok-ng>1:
    mid=(ok+ng)//2
    temp=0
    flag=0
    for i in range(n):
        a=mid//F[i]
        if a>A[i]:
            continue
        else:
            temp+=A[i]-a
    if temp>k:
        flag=1
    if flag:
        ng=mid
    else:
        ok=mid

print(ok)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
N = int(input().strip())
N = list(map(int, str(N)[::-1]))
before = 0
ans = 0
L = len(N)
for i, c in enumerate(N):
    n = c + before
    if 0 <= n < 5:
        before = 0
        ans += n
    elif n == 5:
        if i+1 == L:
            before = 0
            ans += n
            continue
        if N[i+1] < 5:
            before = 0
            ans += n
        else:
            ans += 10-n
            before = 1
    else:
        ans += 10-n
        before = 1
print(ans + before)



### FIXED CODE ###

import sys

input = sys.stdin.readline
N = list(map(int, input().strip()))[::-1]
ans = 0
before = 0
L = len(N)
for i, c in enumerate(N):
    n = c + before
    if 0 <= n < 5:
        before = 0
        ans += n
    elif n == 5:
        if i+1 == L:
            before = 0
            ans += n
            continue
        if N[i+1] < 5:
            before = 0
            ans += n
        else:
            ans += 10-n
            before = 1
    else:
        ans += 10-n
        before = 1
print(ans + before)
### BUGGY CODE ###

n, k = map(int, input().split())
a = [min(i, k) for i in sorted(list(map(int, input().split())))]
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        for j in range(k, -1, -1):
            if j >= a[i]:
                dp[j] = dp[j] | dp[j-a[i]]

    #print(dp)
    if sum(dp[max(0, k - a[mi-1]):k]):
        ba = mi
    else:
        fr = mi

print(fr)

### FIXED CODE ###

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)
### BUGGY CODE ###

N = int(input())
# A[0]
A = [int(input())-1]
 
count = [-1]*N
n = 0
ans = 1
for k in range(N+1):
  if A[n] == 2-1:
    break
  
  elif A[n]+1 > len(A):
    for _ in range(A[n]+1 - len(A)):
      A.append(int(input()) -1)
    continue
  
  
  elif A[n] in count:
    ans = -1
    break
  
  else:
    count[n] = A[n]
    ans += 1
    n = A[n]
 
print(ans)

### FIXED CODE ###

n = int(input())
al = []
for i in range(n):
    a = int(input())
    al.append(a)
 
al.insert(0, 0)
ans = -1
push = 1
for i in range(1, n+2):
    light = al[push]
    push = light
    if light == 2:
        ans = i
        break
print(ans)
### BUGGY CODE ###

import math

q = int(input())
cnt = [0] * (5 * 10 ** 4)
cnt[1] = 1
cnt[2] = 2


def is_prime(n):
    visit = []
    if n % 2 == 0:
        return 0
    for i in range(3, 1 + math.ceil(n ** (0.5))):
        if i not in visit:
            if n % i == 0:
                return 0
            else:
                visit.append(i)
    return 1


for i in range(3, 5 * 10 ** 4):
    odd = 2 * i + 1
    if odd % 3 != 1:
        cnt[i] = cnt[i - 1]
    else:
        k = 0
        if is_prime(odd) and is_prime((odd + 1) // 2):
            k = 1
            # print(odd, is_prime(odd), is_prime((odd + 1) // 2))
        cnt[i] = cnt[i - 1] + k
cnt.append(0)
for i in range(q):
    l, r = map(int, input().split())
    print(cnt[(r - 1) // 2] - cnt[(l - 3) // 2])


### FIXED CODE ###

import math

q = int(input())
cnt = [0] * (5 * 10 ** 4)
cnt[1] = 1
cnt[2] = 2


def is_prime(n):
    visit = []
    if n % 2 == 0:
        return 0
    for i in range(3, 1 + math.ceil(n ** (0.5))):
        if i not in visit:
            if n % i == 0:
                return 0
            else:
                visit.append(i)
    return 1


for i in range(3, 5 * 10 ** 4):
    odd = 2 * i + 1
    if odd % 3 != 1 or (odd + 1) % 4 == 0:
        cnt[i] = cnt[i - 1]
    else:
        k = 0
        if is_prime(odd) and is_prime((odd + 1) // 2):
            k = 1
            # print(odd, is_prime(odd), is_prime((odd + 1) // 2))
        cnt[i] = cnt[i - 1] + k
cnt.append(0)
for i in range(q):
    l, r = map(int, input().split())
    print(cnt[(r - 1) // 2] - cnt[(l - 3) // 2])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

DP=[[-1]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        DP[i][j]=min(i,j,N-1-i,N-1-j)

USED=[[0]*N for i in range(N)]

ANS=0
    
for p in P:
    q,r=divmod(p-1,N)
    ANS+=DP[q][r]
    DP[q][r]-=1
    USED[q][r]=1

    Q=[(q,r)]

    while Q:
        x,y=Q.pop()

        for z,w in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
            if 0<=z<N and 0<=w<N:
                if DP[z][w]>DP[x][y]+1-USED[z][w]:
                    DP[z][w]=DP[x][y]+1-USED[z][w]
                    Q.append((z,w))

print(ANS)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

DP=[[0]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        DP[i][j]=min(i,j,N-1-i,N-1-j)

USED=[[1]*N for i in range(N)]
ANS=0

def update(z,w):
    if 0<=z<N and 0<=w<N:
        if DP[z][w]>DP[x][y]+USED[z][w]:
            DP[z][w]=DP[x][y]+USED[z][w]
            Q.append((z,w))
    

for p in P:
    q,r=divmod(p-1,N)
    ANS+=DP[q][r]
    DP[q][r]-=1
    USED[q][r]=0

    Q=[(q,r)]

    while Q:
        x,y=Q.pop()

        update(x+1,y)
        update(x-1,y)
        update(x,y+1)
        update(x,y-1)

print(ANS)
### BUGGY CODE ###

n,m=map(int,input().split())
lr = [list(map(int,input().split())) for _ in range(m)]
s = {i:0 for i in range(1,n+1)}
cnt = 0
for i in range(m):
    for j in range(lr[i][0],lr[i][1]+1):
        s[j] += 1
for v in s.values():
    if v == m:cnt += 1
print(cnt)

### FIXED CODE ###

n,m=map(int,input().split())
l = [0]*m
r = [0]*m
for i in range(m):
    l[i],r[i] = map(int,input().split())
print(max(min(r) - max(l) + 1, 0))
### BUGGY CODE ###

N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
X0 = [0 for x in X if x == 0]
Xp = [x for x in X if x > 0]
Xm = [-x for x in X if x < 0]
limit = min(sum(Xp), sum(Xm))
Xp = [x for x in Xp if x <= limit]
Xm = [x for x in Xm if x <= limit]
R = [[0, 0] for x in range(limit + 1)]
def c(X, k):
  Q = [0]
  for x in X:
    Q += [q + x for q in Q if q + x <= limit]
  for q in Q:
    R[q][k] += 1
c(Xp, 0)
c(Xm, 1)
print(sum([r[0] * r[1] for r in R]) * (2 ** len(X0)) - 1)

### FIXED CODE ###

from collections import Counter
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
C = Counter([0])
for x in X:
  tmp = Counter()
  for i, c in C.items():
    tmp[i + x] += c
  C += tmp
print(C[0] - 1)
### BUGGY CODE ###

# coding: utf-8

n = int(input())

A = [int(input()) for _ in range(n)]

max_a = max(A)

for i in range(n):
    if max_a == A[i]:
        print(max(A[0:i] + A[i+1:n]))
    else:
        print(max_a)

### FIXED CODE ###

# coding: utf-8

n = int(input())

A = [int(input()) for _ in range(n)]

s_A = sorted(A, reverse=True)

max_a, second_a = s_A[0], s_A[1]

for i in range(n):
    if A[i] == max_a:
        print(second_a)
    else:
        print(max_a)
### 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())
count = 0
for i in range(N+1):
    count += (i * len(make_divisors(i)))

print(count)
    

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    ans += (N//i)*(i+(i*(N//i)))//2
print(ans)
### BUGGY CODE ###

r,g,b,n=list(map(int,input().split()))
cnt=0
for i in range(n+1):
        for j in range(n+1):
                z=n-(i*r+j*g)
                if 0<=z and z%b==0:
                        #print(i,j,z)
                        cnt+=1
print(cnt)

#101


### FIXED CODE ###

r,g,b,n=list(map(int,input().split()))
cnt=0
for i in range(n+1):
        for j in range(n+1):
                z=n-(i*r+j*g)
                if 0<=z and z%b==0:
                        #print(i,j,z)
                        cnt+=1
print(cnt)
### BUGGY CODE ###

# import statistics
N = int(input())
A = list(map(int,input().split()))
# mode = statistics.mode(A)
# print(mode)
# tar = mode
B = []
for a in A:
    count1 = A.count(a)
    count2 = A.count(a+1)
    count3 = A.count(a-1)
    cnt = count1 + count2 + count3
    B.append(cnt)
print(max(B))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
c = []
for i in A:
    c.extend([i-1,i,i+1])
ans = Counter(c).most_common()
print(ans[0][1])
### BUGGY CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    sh, sw = map(lambda x: int(x) - 1, input().split())
    gh, gw = map(lambda x: int(x) - 1, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]

    maze = [[f_inf] * W for _ in range(H)]
    maze[sh][sw] = 0
    que = deque([[sh, sw]])
    while que:
        h, w = que.popleft()
        for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            if grid[next_h][next_w] == ".":
                if maze[next_h][next_w] > maze[h][w]:
                    maze[next_h][next_w] = maze[h][w]
                    que.append([next_h, next_w])
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                next_h, next_w = h + dh, w + dw
                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    continue
                if grid[next_h][next_w] == ".":
                    if maze[next_h][next_w] > maze[h][w] + 1:
                        maze[next_h][next_w] = maze[h][w] + 1
                        que.append([next_h, next_w])
    print(maze[gh][gw] if maze[gh][gw] != f_inf else -1)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    sh, sw = map(lambda x: int(x) - 1, input().split())
    gh, gw = map(lambda x: int(x) - 1, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]

    maze = [[f_inf] * W for _ in range(H)]
    maze[sh][sw] = 0
    que = deque([[sh, sw]])
    while que:
        h, w = que.popleft()
        for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            if grid[next_h][next_w] == ".":
                if maze[next_h][next_w] > maze[h][w]:
                    maze[next_h][next_w] = maze[h][w]
                    que.appendleft([next_h, next_w])
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                next_h, next_w = h + dh, w + dw
                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    continue
                if grid[next_h][next_w] == ".":
                    if maze[next_h][next_w] > maze[h][w] + 1:
                        maze[next_h][next_w] = maze[h][w] + 1
                        que.append([next_h, next_w])
    print(maze[gh][gw] if maze[gh][gw] != f_inf else -1)


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

import sys

n, m, k = map(int, sys.stdin.readline().split())
ab = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
cd = [tuple(map(int, sys.stdin.readline().split())) for _ in range(k)]
friend = [set() for _ in range(n+1)]
for a, b in ab:
    friend[a].add(b)
    friend[b].add(a)
block = [set() for _ in range(n+1)]
for c, d in cd:
    block[c].add(d)
    block[d].add(c)

root = list(range(n+1))
size = [1] * (n + 1)
height = [1] * (n + 1)

def find_root(u):
    v = root[u]
    if v == u:
        return u 
    w = find_root(v)
    root[u] = w 
    return w 

def unite(u, v):
    ru = find_root(u)
    rv = find_root(v)
    if ru != rv:
        if height[ru] >= height[rv]:
            root[rv] = ru 
            height[ru] = max(height[ru], height[rv] + 1)
            size[ru] += size[rv]
        else:
            root[ru] = rv 
            size[rv] += size[ru]

def main():
    for u in range(1, n+1):
        for v in friend[u]:
            unite(u, v)
    
    g = [set() for _ in range(n+1)]
    for i in range(1, n+1):
        find_root(i)
        g[root[i]].add(i)
    
    for i in range(1, n+1):
        yield len(g[root[i]] - friend[i] - block[i]) - 1

if __name__ == '__main__':
    ans = main()
    print(*ans, sep=' ')

### FIXED CODE ###

import sys

n, m, k = map(int, sys.stdin.readline().split())
ab = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
cd = [tuple(map(int, sys.stdin.readline().split())) for _ in range(k)]
friend = [[] for _ in range(n+1)]
for a, b in ab:
    friend[a].append(b)
    friend[b].append(a)
block = [[] for _ in range(n+1)]
for c, d in cd:
    block[c].append(d)
    block[d].append(c)

root = list(range(n+1))
size = [1] * (n + 1)
height = [1] * (n + 1)

def find_root(u):
    v = root[u]
    if v == u:
        return u 
    w = find_root(v)
    root[u] = w 
    return w 

def unite(u, v):
    ru = find_root(u)
    rv = find_root(v)
    if ru != rv:
        if height[ru] >= height[rv]:
            root[rv] = ru 
            height[ru] = max(height[ru], height[rv] + 1)
            size[ru] += size[rv]
        else:
            root[ru] = rv 
            size[rv] += size[ru]

def main():
    for u in range(1, n+1):
        for v in friend[u]:
            unite(u, v)

    for u in range(1, n+1):
        find_root(u)

    for u in range(1, n+1):
        ru = root[u]
        cnt = size[ru] - 1  - len(friend[u])
        for v in block[u]:
            if root[v] == ru:
                cnt -= 1
        yield cnt

if __name__ == '__main__':
    ans = main()
    print(*ans, sep=' ')
### BUGGY CODE ###

def main():
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 1000000007
  from collections import defaultdict
  from fractions import Fraction

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int,{})
  dd_ab = defaultdict(int,{})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      dd_ba[Fraction(-b, a)] += 1
      dd_ab[Fraction(a, b)] += 1


  ans = (2**zero_one_count + 2**one_zero_count -1)
  flag_dd = defaultdict(bool,{})

  for key,value in dd_ba.items():
    if flag_dd[key]:
      continue
    ans *= (2**dd_ab[key] + 2**value - 1) % MOD
    ans %= MOD
    flag_dd[Fraction(key.denominator, -(key.numerator))] = True

  ans += zero_zero_count - 1
  print(ans%MOD) 

main()

### FIXED CODE ###

def main():
  from math import gcd
  from collections import defaultdict
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      if a * b < 0:
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        dd_ba[(b//g, a//g)] += 1
      else:
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        dd_ba[(-b//g, a//g)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  dd_flag = defaultdict(bool, {})

  for key,value in tuple(dd_ba.items()):
    if dd_flag[key]:
      continue
    
    key_0 = key[0]
    key_1 = key[1]
    if key_0<0:
      x = (key_1, -key_0)
    else:
      x = (-key_1, key_0)
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    dd_flag[x] = True

  ans += zero_zero_count - 1
  print(ans%MOD) 

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

N = int(input())

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

ans = 1
for i in range(N):
    ans = ans * A[i]

if (ans > 10 ** 18):
    ans = -1

print(ans)

### FIXED CODE ###

N = int(input())

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

ans = 1

if min(A) == 0:
    ans = 0
else:
    for i in range(N):
        ans = ans * A[i]
        if (ans > 10 ** 18):
            ans = -1
            break

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

from itertools import permutations

d, g = map(int, input().split())
g //= 100
pcs = []
for i in range(d):
    p, c = map(int, input().split())
    c //= 100
    pcs.append((p, c, (i + 1) * p, (i + 1) * p + c))

ans = float('inf')
caches = []
for perm in permutations(range(d)):
    flag = False
    for cache in caches:
        if perm[:len(cache)] == cache:
            flag = True
    if flag:
        continue
    h = g
    tmp = 0
    cache = []
    for i in perm:
        cache.append(i)
        p, c, a, b = pcs[i]
        if h <= a:
            q = (h - 1) // (i + 1) + 1
            tmp += q
            break
        tmp += p
        h -= b
        if h <= 0:
            break
        if tmp >= ans:
            break
    ans = min(ans, tmp)
    caches.append(cache)
print(ans)


### FIXED CODE ###

import bisect
from operator import itemgetter

d, g = map(int, input().split())
g //= 100
problem_quantities = []
complete_scores = []
for i in range(1, d + 1):
    p, c = map(int, input().split())
    c //= 100
    problem_quantities.append(p)
    complete_scores.append(i * p + c)

curr_idx = d
curr_bit = 0
curr_cmp, curr_qtt = 0, 0
complete_combinations = [None] * (1 << d)
complete_combinations[0] = (0, 0, 0)
for use in range(1, 1 << d):
    if use & curr_bit == 0:
        curr_idx -= 1
        curr_bit = use
        curr_cmp = complete_scores[curr_idx]
        curr_qtt = problem_quantities[curr_idx]
    ps, pq, _ = complete_combinations[use ^ curr_bit]
    complete_combinations[use] = (ps + curr_cmp, pq + curr_qtt, use)

complete_combinations.sort()

bi = bisect.bisect(complete_combinations, (g,))

ans = float('inf')
for s, p, use in complete_combinations[:bi]:
    i = d
    while use & 1:
        i -= 1
        use >>= 1
    cmp = complete_scores[i - 1]
    remain = g - s
    if remain >= cmp:
        continue
    q = min(problem_quantities[i - 1], (remain - 1) // i + 1)
    ans = min(ans, p + q)

ans = min(ans, min(map(itemgetter(1), complete_combinations[bi:])))
print(ans)