CodeEff/ECCO huggingface dataset:
# Original solution
import sys
import math


def main():
    """
    2 <= K <= N <= 10^5
    1 <= ai <= N
    1 <= i <= N
    """
    N, K = list(map(int, input().split()))
    *A, = list(map(int, input().split()))

    ans = f_K(N, K, A)
    #ans = editorial(N, K, A)
    print(ans)


def test_examples():
    nka_ans = [
        (4, 3, [2, 3, 1, 4], 2),
        (3, 3, [1, 2, 3], 1),
        (8, 3, [7, 3, 1, 8, 4, 6, 2, 5], 4),
    ]

    for N, K, A, ans in nka_ans:
        assert editorial(N, K, A) == ans
        assert f_K(N, K, A) == ans


def test_ans():
    nka_ans = [
        (5, 2, [1, 2, 3, 4, 5], 4),
        (5, 3, [1, 2, 3, 4, 5], 2),
        (5, 2, [5, 4, 3, 2, 1], 4),
        (5, 3, [5, 4, 3, 2, 1], 2),
    ]

    for N, K, A, ans in nka_ans:
        assert editorial(N, K, A) == ans
        assert f_K(N, K, A) == ans


def f_K(N, K, A):
    """
    最初に置く範囲は、 1_idx - K + 1 から 1_idx
    """
    idx = [i for i, a in enumerate(A) if a == 1][0]
    left_idx = max(0, idx - K)
    ans = float("inf")
    for i in range(left_idx, idx + 1):
        left = i
        right = max(0, N - left - K)
        tmp = (left + (K - 1) - 1) // (K - 1)
        tmp += 1
        tmp += (right + (K - 1) - 1) // (K - 1)
        ans = min(ans, tmp)

    return ans


if __name__ == '__main__':
    main()


# Optimized solution
import sys
import math


def main():
    """
    2 <= K <= N <= 10^5
    1 <= ai <= N
    1 <= i <= N
    """
    N, K = list(map(int, input().split()))
    *A, = list(map(int, input().split()))

    #ans = f_K(N, K, A)
    ans = editorial(N, K, A)
    print(ans)


def test_examples():
    nka_ans = [
        (4, 3, [2, 3, 1, 4], 2),
        (3, 3, [1, 2, 3], 1),
        (8, 3, [7, 3, 1, 8, 4, 6, 2, 5], 4),
    ]

    for N, K, A, ans in nka_ans:
        assert editorial(N, K, A) == ans
        assert f_K(N, K, A) == ans


def test_ans():
    nka_ans = [
        (5, 2, [1, 2, 3, 4, 5], 4),
        (5, 3, [1, 2, 3, 4, 5], 2),
        (5, 2, [5, 4, 3, 2, 1], 4),
        (5, 3, [5, 4, 3, 2, 1], 2),
    ]

    for N, K, A, ans in nka_ans:
        assert editorial(N, K, A) == ans
        assert f_K(N, K, A) == ans


def f_K(N, K, A):
    """
    最初に置く範囲は、 1_idx - K + 1 から 1_idx
    """
    idx = [i for i, a in enumerate(A) if a == 1][0]
    left_idx = max(0, idx - K)
    ans = float("inf")
    for i in range(left_idx, idx + 1):
        left = i
        right = max(0, N - left - K)
        tmp = (left + (K - 1) - 1) // (K - 1)
        tmp += 1
        tmp += (right + (K - 1) - 1) // (K - 1)
        ans = min(ans, tmp)

    return ans


def editorial(N, K, A):
    """
    端から端までカバーしていく
        K + (K - 1) * N (N >= 0)
        これは仮に１番左に1があったとき
    結果的には順番は気にしなくて良い
    上記でカバーしていくと、いつかは最初の1をカバーする
        カバーした順番を1をカバーしたことを最初に行えば変わらない

    TODO: editorial pdfの意味
        1 + g(K − 1) ≤ p ≤ 1 + (g + 1)(K − 1) なる整数 g
    """
    return ((N-1) + (K-1) - 1) // (K-1)



if __name__ == '__main__':
    main()
# Original solution
N, K = list(map(int,input().split()))
A = list(map(int,input().split()))
print(((N-2)//(K-1)+1))

# Optimized solution
N, K = list(map(int,input().split()))
print(((N-2)//(K-1)+1))
# Original solution
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = ((N - 1) + (K - 1 - 1)) // (K - 1)
print(ans)


# Optimized solution
N, K = list(map(int, input().split()))
ans = 1 + ((N - K) + (K - 2)) // (K - 1)
print(ans)
# Original solution
from collections import Counter
from math import *
N, K = [int(x) for x in input().strip().split()]
A = [int(x) for x in input().strip().split()]
A.sort()
c = Counter(A)
minc = c[A[0]]
res = len(A) - minc
print((ceil(res/(K-1))))

# Optimized solution
from math import *
N, K = [int(x) for x in input().strip().split()]
print((ceil((N-1)/(K-1))))
# Original solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(eval(input()))
def LS(): return input().split()
def S(): return eval(input())

def main():
  a,b=LI()
  l=LI()

  c=1
  _b=b
  while True:
    if a<=_b:
      break
    else:
      _b+=b-1
      c+=1

  return c

print((main()))


# Optimized solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(eval(input()))
def LS(): return input().split()
def S(): return eval(input())

def main():
  n,k=LI()
  l=LI()

  c=1
  n-=k

  while True:
    if n<=0:
      break

    n-=(k-1)
    c+=1

  return c

print((main()))
# Original solution
N,K = (int(X) for X in input().split())
A  = [int(X) for X in input().split()]
Left  = A.index(1)
Right = (N-1)-Left
Count = (Right%(K-1)!=0)+Right//(K-1)
Left  -= (Right%(K-1)!=0)*((K-1)-Right%(K-1))
Count += (Left%(K-1)!=0)+Left//(K-1)
print(Count)

# Optimized solution
N,K = (int(X) for X in input().split())
A  = [int(X) for X in input().split()]
Left  = A.index(1)
Right = (N-1)-Left
Count = (Right%(K-1)!=0)+Right//(K-1)
Left -= ((K-1)-Right%(K-1))%(K-1)
Count += (Left%(K-1)!=0)+Left//(K-1)
print(Count)
# Original solution
n,k = list(map(int,input().split()))
a_ = list(map(int,input().split()))
if (n-1)%(k-1) == 0:
    print(((n-1)//(k-1)))
else:
    print(((n-1)//(k-1)+1))

# Optimized solution
n,k = list(map(int,input().split()))
A = n-1
B = k-1
print(((A+(B-1))//B))
# Original solution
import sys
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort()
start = 0
end = k
count = 0
for i in range(n):
    if all(x==1 for x in a):
        print(count)
        sys.exit()
    a[start:end] = [1]*k
    start += (k-1)
    end += (k-1)
    count += 1

# Optimized solution
import sys
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort()
start = 0
end = k
count = 0
for i in range(n):
    if a[n-1]==1:
        print(count)
        sys.exit()
    a[start:end] = [1]*k
    start += (k-1)
    end += (k-1)
    count += 1
# Original solution

def read_input():
    D = int(eval(input()))
    C = input().split()
    C = [int(i) for i in C]
    S = [list(map(int, input().split())) for _ in range(D)]
    T = [int(eval(input())) for _ in range(D)]
    return D, C, S, T


def scoring(S, D, T, C):
    res = []
    last = [0 for _ in range(26)]
    final = 0
    for i in range(D):
        dec = 0
        for j in range(26):
            for loc, val in enumerate(T[:i + 1]):
                if val == j + 1:
                    last[j] = loc + 1
            dec += C[j] * (i - last[j] + 1)
        final += S[i][T[i] - 1] - dec
        res.append(final)
    return res


D, C, S, T = read_input()
res = scoring(S, D, T, C)
for x in res:
    print(x)


# Optimized solution
def read_input():
    D = int(eval(input()))
    C = input().split()
    C = [int(i) for i in C]
    S = [list(map(int, input().split())) for _ in range(D)]
    T = [int(eval(input())) for _ in range(D)]
    return D, C, S, T


def scoring(S, D, T, C):
    res = []
    last = [0 for _ in range(26)]
    final = 0
    for i in range(D):
        dec = 0
        last[T[i] - 1] = i + 1
        for j in range(26):
            dec += C[j] * (i - last[j] + 1)
        final += S[i][T[i] - 1] - dec
        res.append(final)
    return res


D, C, S, T = read_input()
res = scoring(S, D, T, C)
for x in res:
    print(x)
# Original solution
D = int(eval(input()))
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]
t = [int(eval(input())) for _ in range(D)]

last = [0 for _ in range(26)]

value = 0
for i in range(D):
  day = i + 1
  value += s[i][t[i]-1]
  last[t[i]-1] = day
  for j in range(26):
    value -= c[j] * (day - last[j])
  print(value)

# Optimized solution
D = int(eval(input()))
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]
t = [int(eval(input())) for _ in range(D)]

def calc(D, s, t):
  last = [0 for _ in range(26)]
 
  value = 0
  for i in range(D):
    day = i + 1
    value += s[i][t[i]-1]
    last[t[i]-1] = day
    for j in range(26):
      value -= c[j] * (day - last[j])
    print(value)
calc(D, s, t)
# Original solution
D = int(eval(input()))
c = [int(i) for i in input().split()]
s = [[int(i) for i in input().split()] for _ in range(D)]
t = [int(eval(input()))-1 for _ in range(D)]
ans = 0
llst = [0]*26
def last(d,i): return llst[i]

for day,i in enumerate(list(range(D)),1):
    llst[t[i]] = day
    ans += s[i][t[i]]
    for j in range(26): ans -= c[j]*(day-last(day,j))
    print(ans)

# Optimized solution
D = int(eval(input()))
c = [int(i) for i in input().split()]
s = [[int(i) for i in input().split()] for _ in range(D)]
t = [int(eval(input()))-1 for _ in range(D)]
ans = 0
llst = [0]*26

for day,i in enumerate(list(range(D)),1):
    llst[t[i]] = day
    ans += s[i][t[i]]
    for j in range(26): ans -= c[j]*(day-llst[j])
    print(ans)
# Original solution
import bisect
import random
import sys

input = sys.stdin.readline


class score:
    def __init__(self, t):
        self.t = t

    def first_score(self):
        last = [0]*26
        score = 0
        for i,ti in enumerate(self.t):
            score += S[i][ti - 1]
            last[ti-1] = i + 1
            for j in range(26):
                score -= C[j] * ((i+1) - last[j])
        self.score = score
        return score


D = int(eval(input()))
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for i in range(D)]

#T = [int(input()) for i in range(D)]
T = []
for i in range(D):
    T.append(int(eval(input())))
    s = score(T)
    print((s.first_score()))

# Optimized solution
from bisect import bisect_left


class score:
    def __init__(self,t) -> None:
        self.t = t
        score = 0
        last = [[] for i in range(26)]
        for i,ti in enumerate(t):
            score += s[i][ti-1]
            last[ti-1].append(i+1)
            for tj in range(26):
                if last[tj-1] == []:
                    score -= c[tj-1]*(i+1)
                else:
                    #print(last)
                    score -= c[tj-1]*((i+1)-last[tj-1][-1])
            print(score)
        self.score = score
    def a__init__(self,t) -> None:
        score = 0
        last = [[] for i in range(26)]
        for i,ti in enumerate(t):
            # 開催分を加算
            score += s[i][ti-1]
            # 減らす
            if last[ti-1] == []:
                score -= c[i]*i+1
            else:
                score -= c[i]*((i+1)-last[ti-1][-1])
            last[ti-1].append(i+1)
            print(score)
        for i in range(26):
            if last[i] == []:
                score -= c[i]*D
            else:
                score -= c[i]*(D-last[i][-1])
        self.score = score
        self.t = t


D = int(eval(input()))
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for i in range(D)]
t = [int(eval(input())) for i in range(D)]

sc = score(t)
#print(sc.score)
# Original solution
n = int(eval(input()))
a,b = list(map(int,input().split()))
l = list(map(int,input().split()))
c = [0,0,0]
for i in l:
    if i <= a:
        c[0] += 1
    elif i > b:
        c[2] += 1
    else:
        c[1] += 1
print((min(c)))

# Optimized solution
n=int(eval(input()))
a,b=list(map(int, input().split()))
p=list(map(int, input().split()))
c=[0]*3
for i in p:
       if i <=a:
        c[0] +=1
       elif i>b:
        c[2] +=1
       else:
        c[1]+=1
print((min(c)))
# Original solution
def main():
    N = int(eval(input()))
    A, B = (int(i) for i in input().split())
    P = [int(i) for i in input().split()]
    cnt = [0, 0, 0]
    for p in P:
        if p <= A:
            cnt[0] += 1
        elif p <= B:
            cnt[1] += 1
        else:
            cnt[2] += 1
    print((min(cnt)))


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    N = int(eval(input()))
    A, B = (int(i) for i in input().split())
    P = [int(i) for i in input().split()]

    cnt = [0]*3
    for p in P:
        if p <= A:
            cnt[0] += 1
        elif p <= B:
            cnt[1] += 1
        else:
            cnt[2] += 1

    print((min(cnt)))


if __name__ == '__main__':
    main()
# Original solution
print(input().strip()[::-1])

# Optimized solution
print(input()[::-1])
# Original solution
str = input()
str_lis = list(str)
str_lis.reverse()
print((''.join(str_lis)))

# Optimized solution
line = input()
lis = ['' for i in range(len(line))]
for i in range(len(line)-1, -1, -1):
    lis[len(line)-1-i] = line[i]
else:
    print(''.join(lis))
# Original solution
import math

if __name__ == "__main__":
    deg = int(eval(input()))
    print((360//math.gcd(deg, 360)))

# Optimized solution
def lcm(x, y):
   if x > y:
       greater = x
   else:
       greater = y
 
   while(True):
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1
 
   return lcm
x = int(eval(input()))
if 360%x == 0:
    print((int(360/x)))
else :
    print((int(lcm(360,x)/x)))
# Original solution
import math
n=int(eval(input()))
print((360//math.gcd(n,360)))

# Optimized solution
import math
print((360//math.gcd(int(eval(input())),360)))
# Original solution
import math
x=int(eval(input()))
print((360//math.gcd(360,x)))

# Optimized solution
x = int(eval(input()))
print(([360*n//x for n in range(1, 500) if 360 * n % x == 0][0]))
# Original solution
import math
#print(math.cos(math.radians(90)))
#exit()
n = int(eval(input()))
x = 0
y = 1
deg = 90 - n
cnt = 1
#print(x<-10**(-5))
while 1 == 1:
    x += math.cos(math.radians(deg))
    y += math.sin(math.radians(deg))
    deg -= n
    cnt += 1
    if x > -10**(-5) and x < 10**(-5) and y > -10**(-5) and y < 10**(-5):
        break
print(cnt)

# Optimized solution
import math
#print(math.cos(math.radians(90)))
#exit()
x = int(eval(input()))
print((360//math.gcd(360,x)))
# Original solution
x = int(eval(input()))

ans = 360//x
x = 360 % x

while x != 0:
    ans += 360//x
    x %= 360

print(ans)


# Optimized solution
x = int(eval(input()))

ans = 0

while True:
    ans += 1
    if ans*x % 360 == 0:
        break

print(ans)
# Original solution
X = int(eval(input()))

x = [0]
y = [0]
t = X
ans = 1
while True:
    ans += 1
    x.append(t)
    y.append(t)
    if (180-t)%360 in x:
        if t == (180-t)%360 and x.count(t) == 1:
            t += X
            t %= 360
            continue
        x.remove((180-t)%360)
        x.remove(t)
    elif (180+t) in x:
        if t == (180+t)%360 and x.count(t) == 1:
            t += X
            t %= 360
            continue
        x.remove((180-t)%360)
        x.remove(t)
    if (-t)%360 in y:
        if t == (-t)%360 and y.count(t) == 1:
            t += X
            t %= 360
            continue
        y.remove((-t)%360)
        y.remove(t)
    elif (180+t) in y:
        if t == (180-t)%360 and y.count(t) == 1:
            t += X
            t %= 360
            continue
        y.remove((180-t)%360)
        y.remove(t)
    if len(x) == 0 and len(y) == 0:
        break
    t += X
    t %= 360
print((ans//2))

# Optimized solution
X = int(eval(input()))

ans = 360
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

ans = 360 // gcd(X, 360)
print(ans)
# Original solution
import math
X = int(eval(input()))
lcm = 360 * X // math.gcd(360, X)
print((lcm // X))

# Optimized solution
import math
X = int(eval(input()))
# lcm = 360 * X // math.gcd(360, X)
print((360 // math.gcd(360, X)))
# Original solution
# import matplotlib.pyplot as plt
import math

def squaredDistance(a, b):
  return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

# for X in range(1, 180):
angle = 90
X = int(eval(input()))
iter = 0
current = [0, 0]
previous = current

while (iter == 0 or squaredDistance(current, [0, 0]) > 0.00001):
  if (iter > 500):
    break

  dir = [math.cos(math.radians(angle)), math.sin(math.radians(angle))]
  current = [current[0] + dir[0], current[1] + dir[1]]
  angle = (angle + X) % 360
  # plt.plot([previous[0], current[0]], [previous[1], current[1]])
  previous = current
  iter = iter + 1

  # plt.show()

print(iter)
  # print("X = {} : {}".format(X, iter))



# Optimized solution
# import matplotlib.pyplot as plt
import math
 
def lcm(x, y):
   if x > y:
       z = x
   else:
       z = y
 
   while(True):
       if((z % x == 0) and (z % y == 0)):
           lcm = z
           break
       z += 1
 
   return lcm

X = int(eval(input()))
print((int(lcm(X, 360) / X)))
# Original solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    x = I()

    c = collections.defaultdict(int)
    r = 0
    t = -x
    while True:
        r += 1
        t += x
        t %= 360
        if t >= 180:
            c[t - 180] -= 1
        else:
            c[t] += 1

        if all(v == 0 for v in c.values()):
            return r

    return -1


print(main())




# Optimized solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    x = I()

    g = math.gcd(x, 360)

    return 360 // g


print(main())
# Original solution
import math
X=int(eval(input()))
shukai=360
while True:
    if shukai%X==0:
        print((shukai//X))
        exit()
    else:
        shukai*=2

# Optimized solution
def gcda(a,b):
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    return gcda(r, b)

def lcm(a,b):
    return a*b//gcda(a,b)

X=int(eval(input()))
shukai=360
while True:
    if shukai%X==0:
        print((shukai//X))
        exit()
    else:
        shukai=lcm(shukai,X)
# Original solution
import math
from fractions import Fraction

x = int(eval(input()))
rad = Fraction((math.pi / 180) * x)

k = 0
while True:
    k += 1
    s = rad * k
    if s % (math.pi * 2) == 0:
        break
print(k)

# Optimized solution
import math
from fractions import Fraction

x = int(eval(input()))


k = 0
while True:
    k += 1
    s = x * k
    if s % 360 == 0:
        break
print(k)
# Original solution
x = int(eval(input()))

for k in range(1, 10000):
    if x*k % 360 == 0:
        print(k)
        break


# Optimized solution
x = int(eval(input()))


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

  
n = gcd(x, 360)
print((360//n))
# Original solution
from math import gcd

x = int(eval(input()))
y = x * 360 // gcd(x, 360)
print((y//x))

# Optimized solution
x = int(eval(input()))
y = 0
k = 0
while True:
    y += x
    k += 1
    if y % 360 == 0:
        break
print(k)
# Original solution
x=int(eval(input()))
i=1
if 1<=x<=179:
	while True:
		if 360/x==int(360/x):
			print((int(360/x)))
			break
		else:
			i+=1



# Optimized solution
x=int(eval(input()))
i=1
if 1<=x<=179:
	while True:
		if 360*i%x==0:
			print((int(360*i/x)))
			break
		else:
			i+=1
# Original solution
import math

n = int(eval(input()))
ab = []
for i in range(n):
  ab.append(tuple(map(int,input().split())))
MOD = 1000000007

d = {}
zero = 0
for a,b in ab:
  if a == 0 and b == 0:
    zero += 1
    continue
  g = math.gcd(a,b)
  a //= g
  b //= g
  if b < 0:
    a,b = -a,-b
  elif a < 0 and b == 0:
    a = -a
  rot90 = False
  if a <= 0:
    a,b = b,-a
    rot90 = True
  if (a,b) in d:
    if rot90:
      d[(a,b)][1] += 1
    else:
      d[(a,b)][0] += 1
  else:
    if rot90:
      d[(a,b)] = [0,1]
    else:
      d[(a,b)] = [1,0]
#print(d)

ans = 1
for k,v in list(d.items()):
  tmpans = pow(2,v[0],MOD)+pow(2,v[1],MOD)-1
  tmpans %= MOD
  ans *= tmpans
ans -= 1
ans += zero
print((ans%MOD))

# Optimized solution
import math

n = int(eval(input()))
ab = []
for i in range(n):
  ab.append(tuple(map(int,input().split())))
MOD = 1000000007

d = {}
zero = 0
for a,b in ab:
  if a == 0 and b == 0:
    zero += 1
    continue
  g = math.gcd(a,b)
  a //= g
  b //= g
  if b < 0:
    a,b = -a,-b
  elif a < 0 and b == 0:
    a = -a
  rot90 = False
  if a <= 0:
    a,b = b,-a
    rot90 = True
  if (a,b) in d:
    if rot90:
      d[(a,b)][1] += 1
    else:
      d[(a,b)][0] += 1
  else:
    if rot90:
      d[(a,b)] = [0,1]
    else:
      d[(a,b)] = [1,0]
#print(d)

ans = 1
for k,v in list(d.items()):
  tmpans = pow(2,v[0],MOD)+pow(2,v[1],MOD)-1
  tmpans %= MOD
  ans *= tmpans
  ans %= MOD
ans -= 1
ans += zero
print((ans%MOD))