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

N = int(input())
Ps = list(map(int,input().split()))
ans = 0
for n in range(1,N+1):
    if n == 1:
        ans +=1
    elif Ps[n-1] == min(Ps[:n]):
        ans += 1
    else:
        pass
print(ans)


### FIXED CODE ###

N = int(input())
Ps = list(map(int,input().split()))
ans = 0
minP = N
for p in Ps:
    if p <= minP:
        ans += 1
    minP = min(minP, p)
print(ans)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
l=[]
for i in range(N):
  val=A.pop(i)
  num=max(A)
  l.append(num)
  A.insert(i,val)
  
for i in range(N):
  print(l[i])

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
max_val=max(A)

def f(A):
  for i in range(N):
    if A[i]==max_val:
      n=i
    else:
      pass
   
  return n
n=f(A)
l=[max_val]*N
A.pop(n)
second_max=max(A)
l[n]=second_max

for i in range(N):
  print(l[i])
### BUGGY CODE ###

n = int(input())
x = list(map(int,input().split()))

flag = 1
if n % 2 == 1 :
    for i in range(0,n,2):
        if i == 0 :
            if x.count(i) !=1:
                flag = 0
                break
        elif x.count(i) == 2:
            x.remove(i)
            x.remove(i)
            continue
        else:
            flag = 0
            break
else:
    for i in range(1,n,2):  
        if x.count(i) == 2:
            x.remove(i)
            x.remove(i)
            continue
        else:
            flag = 0
            break
            
if flag == 1:
    ans = 1
    if n >=2:
        for i in range(n // 2 ):
            ans = (ans * 2) % (10 ** 9 + 7)
        
    print(2 ** ((n) // 2 ))
else:
    print(0)
    

### FIXED CODE ###

n = int(input())
x = list(sorted(list(map(int,input().split()))))

flag = 1
if n % 2 == 1 :
    for i in range(0,n):
        if i == 0 :
            co = 0
            if x[i] == 0:
                x[i] = -1

        elif i != 0 and i <= n-2 and (i) % 2 ==1 :
            if x[i] == i+1 and x[i+1] == i+ 1 and (i+1) % 2 == 0:
                x[i] = -1
                x[i+1] = -1
        else:
            continue
else:
    for i in range(0,n):  
        if x[i] == i+1 and x[i+1] == i+ 1 and (i+1) % 2 == 1 and i <= n-2:
            x[i] = -1
            x[i+1] = -1
        else:
            continue
            
if list(set(x)) == [-1]:
    ans = 1
    if n >=2:
        for i in range(n // 2 ):
            ans = (ans * 2) % (10 ** 9 + 7)
        
    print(ans)
else:
    print(0)
### BUGGY CODE ###

n, m = map(int,input().split())
    
tbin_o = []

tbin_1 = []
tbin_n = []
for i in range(m):
    xxx = list(map(int,input().split()))
    if xxx[0] == 1:
        tbin_1.append(xxx[1])
    elif xxx[1] == n :
        tbin_n.append(xxx[0])
    else:
        None

aaa = 0
for i in tbin_1:
    if i in tbin_n:
        aaa = 1
        break

if aaa == 1 :
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

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

boolins =[]
for i in range(n):
    boolins.append(0)
    
for i in range(m):
    xxx = list(map(int,input().split()))
    if xxx[0] == 1:
        boolins[xxx[1]] = boolins[xxx[1]] + 1
    elif xxx[1] == n :
        boolins[xxx[0]]=boolins[xxx[0]]+ 1
    else:
        None


if 2 in boolins:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

#!/usr/bin/env python3

x = int(input())
S = {0}
i = 0
while x not in S:
    i += 1
    S = S | {s - i for s in S} | {s + i for s in S}
print(i)


### FIXED CODE ###

#!/usr/bin/env python3

import math

print(math.ceil((-1 + (8 * int(input()) + 1) ** 0.5) / 2))
### BUGGY CODE ###

N=int(input())
for i in range(1,3501):
    for j in range(1,3501):
        aw=(N*i*j)
        bw=4*i*j-N*i-N*j
        if bw<=0:
            continue
        elif aw%bw==0:
            h=i
            n=j
            break
print(h,n,int(bw/aw))

### FIXED CODE ###

N=int(input())
for i in range(1,3501):
    for j in range(1,3501):
        bw=4*i*j-N*i-N*j
        if bw<=0:
            continue
        if (N*i*j)%bw==0:
            print(i,j,(N*i*j)//bw)
            exit()
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class Graph:
    """
    隣接リストによる無向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))
        self.graph[dst].append((src, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra:
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

    def shortest_distance(self):
        """
        startノードから各ノードまでの最短距離
        """
        return self.dist


def main():
    N,x,y = map(int, readline().split())

    # グラフの構築
    E = Graph()
    for i in range(1,N):
        if i == x:
            E.add_edge(x, y)
        E.add_edge(i, i+1)
    
    # 各頂点についてダイクストラ
    count = [0]*N
    for i in range(1,N):
        D = Dijkstra(E, i)
        dist = D.shortest_distance()
        for j in range(i+1,N+1):
            k = dist[j]
            count[k] += 1

    for k in range(1,N):
        print(count[k])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def main():
    N,x,y = map(int, readline().split())

    count = [0]*N
    for i in range(1,N):
        for j in range(i+1,N+1):
            k = min(j-i, abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(j-x))
            count[k] += 1

    for k in range(1,N):
        print(count[k])


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

n=int(input())
P=list(map(int,input().split()))
ans=1
for i in range(n-1):
    now=P.pop(-1)
    if min(P)>now:
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
P=list(map(int,input().split()))
ans=0
m=10**7
for i in range(n):
    if m>P[i]:
        ans+=1
        m=P[i]
print(ans)
### BUGGY CODE ###

l=input()
n=len(l)
mod=1000000007
dp=[2]
ans=(3**(n-1))%mod
for i in range(1,n):
  if l[i]=='0':
    dp.append(dp[-1])
  else:
    dp.append(dp[-1]*2)
    ans+=dp[i-1]*(3**(n-i-1))
    ans=ans%mod
print((ans+dp[n-1])%mod)

### FIXED CODE ###

l=input()
n=len(l)
mod=1000000007
dp=[0]*n
dp[0]=2
ans=[0]*n
ans[0]=1
for i in range(1,n):
  if l[i]=='0':
    dp[i]=(dp[i-1])%mod
    ans[i]=(ans[i-1]*3)%mod
  else:
    dp[i]=(dp[i-1]*2)%mod
    ans[i]=(ans[i-1]*3+dp[i-1])%mod
print((ans[n-1]+dp[n-1])%mod)
### BUGGY CODE ###

n = int(input())
a_arr = []
for i in range(n):
    a_arr.append(list(map(int,input().split())))
cnt = [0]*n
day = 0
while (cnt != [n-1]*n):
    day += 1
    jdg = [0]*n
    for i in range(n):
        if jdg[i] != 0 or cnt[i] == n -1 :
            continue
        tmp = a_arr[i][cnt[i]] - 1 
        if cnt[tmp] < n - 1 and a_arr[tmp][cnt[tmp]] == i + 1 and jdg[tmp] == 0:
            cnt[i] += 1
            cnt[tmp] += 1
            jdg[i] += 1
            jdg[tmp] += 1
    if day > (n-1)*n//2:
        print(-1)
        exit()
print(day)

### FIXED CODE ###

n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
    for j in range(n-1):
        a[i][j] -= 1
    a[i].reverse()
q = []

def check(i):
    if len(a[i]) == 0:
        return 
    j = a[i][-1]
    if len(a[j]) == 0:
        return
    if a[j][-1] == i:
        q.append([min(i,j), max(i,j)])
for i in range(n):
    check(i)
day = 0
while (len(q) > 0):
    day += 1
    prevQ = list(map(list, set(map(tuple, q))))
    q = []
    for i,j in prevQ:
        a[i].pop()
        a[j].pop()
        check(i)
        check(j)
for i in range(n):
    if len(a[i]) > 0:
        print(-1)
        exit()
print(day)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
H,W = map(int,input().split())
Gd,L,R,U,D=[None]*H,[None]*H,[None]*H,[None]*H,[None]*H
for _ in range(H):
  Gd[_] = list(input())
  L[_], R[_], D[_], U[_] = [0]*W, [0]*W, [0]*W, [0]*W
L=np.array(L)
R=np.array(R)
U=np.array(U)
D=np.array(D)
def ma():
  for h in range(H):
    for w in range(W):
      if Gd[h][w]=='#':
        R[h][w]=0
      else:
        if w==0:
          R[h][w]=1
        else:
          R[h][w]=R[h][w-1]+1
      wr=W-w-1
      if Gd[h][wr]=='#':
        L[h][wr]=0
      else:
        if w==0:
          L[h][wr]=1
        else:
          L[h][wr]=L[h][wr+1]+1

  for w in range(W):
    for h in range(H):
      if Gd[h][w]=='#':
        D[h][w]=0
      else:
        if h==0:
          D[h][w]=1
        else:
          D[h][w]=D[h-1][w]+1
      hr=H-h-1
      if Gd[hr][w]=='#':
        U[hr][w]=0
      else:
        if h==0:
          U[hr][w]=1
        else:
          U[hr][w]=U[hr+1][w]+1
  return np.max(D+U+L+R-3)
print(ma())

### FIXED CODE ###

import numpy as np
H,W = map(int,input().split())
HL=list(range(H))
WL=list(range(W))
Gd = np.array([list(input()) for _ in HL])
Gd = np.where(Gd=='.', 1, 0)
L=np.zeros((H,W),dtype=np.int64)
R=np.zeros((H,W),dtype=np.int64)
U=np.zeros((H,W),dtype=np.int64)
D=np.zeros((H,W),dtype=np.int64)

for w in WL:
  R[:,w]=(R[:,w-1]+1)*Gd[:,w]
  L[:,-w-1]=(L[:,-w]+1)*Gd[:,-w-1]
for h in HL:
  D[h,:]=(D[h-1,:]+1)*Gd[h,:]
  U[-h-1,:]=(U[-h,:]+1)*Gd[-h-1,:]
print(np.max(D+U+L+R-3))
### BUGGY CODE ###

import sys

N,*a = map(int,open(0).read().split())
for i in range(1<<N):
    bit_str = list(reversed(str(i).zfill(N)))
    flg = True
    for j in range(N):
        parts_bit = bit_str[j::j+1]
        _sum = 0
        for k in parts_bit:
            _sum += int(k)
        if _sum % 2 != a[j]:
            flg = False
            continue
    if flg:
        ans = []
        for i in range(len(bit_str)):
            if bit_str[i] == "1":
                ans.append(str(i+1))
        print(len(ans))
        print(" ".join(ans))
        sys.exit()
print(-1)  

    

### FIXED CODE ###

from collections import Counter

N,*a = map(int,open(0).read().split())
ans = []
for i in range(N)[::-1]:
    part_rem = sum(a[i::i+1]) % 2
    if a[i] == 0:
        if part_rem == 1:
            a[i] = abs(a[i] - 1) 
    elif a[i] == 1:
        if part_rem == 0:
            a[i] = abs(a[i] - 1)
            
c = Counter(a)            
print(c[1])
for i in range(N):
    if a[i] == 1:
        print(i+1,end=" ")
print()
### BUGGY CODE ###

N = int(input())
S = input()
dp = [0]*N

for i in range(N):
    j = i+1
    while S[i:j] in S[j:N]:
        dp[i] += 1
        j += 1
print(max(dp))

### FIXED CODE ###

N = int(input())
S = input()
dp = [0]*N
j = 1

for i in range(N):
    while S[i:j] in S[j:N]:
        dp[i] = j-i
        j += 1
print(max(dp))
### BUGGY CODE ###

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a1=list(range(n+1))
for f in range(k):
    a1=[0 for s in a1]
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
    if sum(a)==n**2:
        break
for i in range(n):
    print(a[i])

### FIXED CODE ###

from numba import njit

@njit(cache=True)
def aaa(n,k,a):
    for f in range(k):
        a1=[0]*(n+1)
        for x in range(n):
            y=max(0,x-a[x])
            a1[y]=a1[y]+1    
            z=min(n-1,x+a[x])
            a1[z+1]=a1[z+1]-1
        a[0]=a1[0]
        for x in range(1,n):    
            a[x]=a[x-1]+a1[x]
        if a==[n]*n:
            break
    return a

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]

b=aaa(n,k,a)
for i in range(n):
    print(b[i])
### BUGGY CODE ###

N,X,Y = map(int,input().split())
for k in range(1,N):
    S = 0
    for i in range(1,N):
        for j in range(i+1,N+1):
            if (i<= X and j<=X) or (i>=Y and j>=Y):
                if j-i == k:
                    S += 1
            elif i <= X and j >= Y:
                if j-i+X-Y+1 == k:
                    S += 1
            elif i >= X and j <= Y:
                if j-i <= Y-j+i-X+1:
                    if j-i == k:
                        S += 1
                else:
                    if Y-j+i-X+1 == k:
                        S += 1
            elif i <= X and X <= j <= Y:
                if j-i <= X+Y-i-j+1:
                    if j-i == k:
                        S += 1
                else:
                    if X+Y-i-j+1 == k:
                        S += 1
            elif j >= Y and X <= i <= Y:
                if j-i <= -X-Y+i+j+1:
                    if j-i == k:
                        S += 1
                else:
                    if -X-Y+i+j+1 == k:
                        S += 1
            else:
                print(i,j,k)
    print(S)

### FIXED CODE ###

N,X,Y = map(int,input().split())
A = [0 for i in range(N)]
for i in range(N-1):
    a = i+1
    for j in range(i+1,N):
        b = j+1
        A[min([b-a,abs(X-a)+abs(Y-b)+1])] += 1
for i in range(1,N):
    print(A[i])
### BUGGY CODE ###

from collections import Counter
import math


def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

ac = dict(Counter(a))

ans = 0
for k, v in ac.items():
    if v < 2:
        ac[k] = (v, 0, 0)
    else:
        c = nCr(v, 2)
        ans += c
        if v - 1 < 2:
            ac[k] = (v, c, 0)
        else:
            ac[k] = (v, c, nCr(v - 1, 2))

for i in a:
    v = ac[i]
    if v[0] - 1 < 2:
        print(ans - v[1])
    else:
        print(ans - v[1] + v[2])

### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce


def nCr(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


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

ac = dict(Counter(a))

ans = 0
for k, v in ac.items():
    if v < 2:
        ac[k] = (v, 0, 0)
    else:
        c = nCr(v, 2)
        ans += c
        if v - 1 < 2:
            ac[k] = (v, c, 0)
        else:
            ac[k] = (v, c, nCr(v - 1, 2))

for i in a:
    v = ac[i]
    if v[0] - 1 < 2:
        print(ans - v[1])
    else:
        print(ans - v[1] + v[2])
### BUGGY CODE ###

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


pos = 0

for q in range(Q):
  myinput = list(input().split())
  #print(myinput)
  if len(myinput) == 1:
      pos += 1
  else:
      if myinput[1] == '1':
          if pos% 2 == 0:
            #正方向、先頭
            S = myinput[2] + S    
          elif pos%2 !=0:
            #逆方向、先頭
            S += myinput[2]   
      elif myinput[1] == '2':
          if pos% 2 == 0:
              #正方向、末尾
            S += myinput[2]    
          elif pos%2 !=0:
               #逆方向、末尾
                 S = myinput[2] + S    

if pos%2 == 0:                 
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

from collections import deque

S = [input()]
d = deque(S)
#print(d)
Q = int(input())

pos = 0

for q in range(Q):
  myinput = list(input().split())
  #print(myinput)
  if len(myinput) == 1:
      pos += 1
  else:
      if myinput[1] == '1':
          if pos% 2 == 0:
               d.appendleft(myinput[2])   
          elif pos%2 !=0:
              #逆方向、先頭
              d.append(myinput[2])   
      elif myinput[1] == '2':
          if pos% 2 == 0:
              #正方向、末尾
              d.append(myinput[2])   
          elif pos%2 !=0:
              #逆方向、末尾
              d.appendleft(myinput[2])   

if pos%2 == 0:                 
    print(''.join(d))
else:
    print((''.join(d))[::-1])
### BUGGY CODE ###

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

total = 0

for x in range(len(A)):
    for y in range(x+1, len(A)):
        total += A[x]*A[y]
print(total % (10**9+7))


### FIXED CODE ###

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

L = len(A)
total = 0
tmp = 0
mod = 10**9+7
for y in range(L):
    tmp += A[y]

for x in range(L):
    tmp -= A[x] 
    total += tmp*A[x]
print(total % mod)
### BUGGY CODE ###

N, X, Y = map(int, input().split())

dist_from_X = list(abs(i - (X - 1)) for i in range(N))
dist_from_Y = list(abs(i - (Y - 1)) for i in range(N))

ans_list = [0] * N

for i in range(N):
    for j in range(N):
        i_X_Y_j = dist_from_X[i] + 1 + dist_from_Y[j]
        i_Y_X_j = dist_from_Y[i] + 1 + dist_from_X[j]
        i_j = abs(i - j)
        min_dist_i_j = min(i_X_Y_j, i_Y_X_j, i_j)
        ans_list[min_dist_i_j] += 1

for num in ans_list[1:]:
    print(num // 2)


### FIXED CODE ###

N, X, Y = map(int, input().split())

dist_from_X = list(abs(i - (X - 1)) for i in range(N))
dist_from_Y = list(abs(i - (Y - 1)) for i in range(N))

ans_list = [0] * N

for i in range(N):
    for j in range(i, N):
        i_X_Y_j = dist_from_X[i] + 1 + dist_from_Y[j]
        i_Y_X_j = dist_from_Y[i] + 1 + dist_from_X[j]
        i_j = abs(i - j)
        min_dist_i_j = min(i_X_Y_j, i_Y_X_j, i_j)
        ans_list[min_dist_i_j] += 1

for num in ans_list[1:]:
    print(num)
### BUGGY CODE ###

n = int(input())
ary = list(map(int, input().split()))

ary_2 = [ary[0]]
for i in range(1, n):
    ary_2.append(ary[i] + ary_2[i-1])
ary_2 = [0] + ary_2

ans = 0
for j in range(n):
    for k in range(j+1, n+1):
        if ary_2[j] == ary_2[k]:
            ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
ary = list(map(int, input().split()))
#print(n,ary)

ary_2 = [ary[0]]
for i in range(1, n):
    ary_2.append(ary[i] + ary_2[i-1])
ary_2 = [0] + ary_2
#print(ary_2)

from collections import Counter
c = Counter(ary_2)
v = (c.values())
#print(v)

from math import factorial
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

ans = 0
for j in v:
    if j >1:
        ans += combinations_count(j,2)

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

import numpy as np
n = int(input())
ans = 0
for i in range(1, n + 1):
    ans += np.sum(np.arange(i, n+1, i, dtype=np.int64))
print(ans)


### FIXED CODE ###

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

import bisect

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

A.sort()
B.sort()
C.sort()

ans = 0
for i in B:
  a=bisect.bisect_left(A, i)
  c=bisect.bisect_right(C, i)
  ans += len(A[:a])*len(C[c:])
print(ans)

### FIXED CODE ###

import bisect

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

A.sort()
B.sort()
C.sort()

ans = 0
for i in B:
  a=bisect.bisect_left(A, i)
  c=bisect.bisect_right(C, i)
  ans += a*(N-c)
print(ans)
### BUGGY CODE ###

import sys

n,k = map(int,input().split())
x = k+(n%k)
x = n
min = sys.maxsize

while True:
    if x%k == 0:
        min = 0
        break

    x = abs(x-k)
    if x == min :break
    elif x < min : min = x

print(min)



### FIXED CODE ###

import sys

n,k = map(int,input().split())
x = k+(n%k)
min = sys.maxsize

while True:
    if x%k == 0:
        min = 0
        break

    x = abs(x-k)
    if x == min :break
    elif x < min : min = x

print(min)
### BUGGY CODE ###

def main():
  from fractions import Fraction
  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:
      dd_ba[Fraction(-b, a)] += 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
    x = Fraction(key.denominator, -(key.numerator))
    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()

### 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 ###

from itertools import permutations, combinations,combinations_with_replacement,product
import math
from functools import reduce

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

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

def main():
    #n, k = map(int,input().split())
    k = int(input())
    lists = []

    for i in range(k):
        lists.append(int(i+1))
        lists.append(int(i+1))
        lists.append(int(i+1))
    

    lists = list(combinations_with_replacement(lists,3))
    lists = sorted(set(lists))

        
    koubai = 0
    for i in lists:
        if len(set(i))==1:
            koubai = koubai + gcd(i[0],i[1],i[2])
            #print(koubai)
        elif len(set(i))==2:
            koubai = koubai + 3*gcd(i[0],i[1],i[2])
        else:
            koubai = koubai + 6*gcd(i[0],i[1],i[2])
            #print(koubai)
    print(koubai)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import math

def main():
    #n, k = map(int,input().split())
    k = int(input())
    lists = []
    sum = 0
    for i in range(k):
        for j in range(k):
            for l in range(k):
                sum = sum + math.gcd(math.gcd(i+1 ,j+1), l+1)
    print(sum)

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

import sys
sys.setrecursionlimit(10**6)
N, K = map(int, input().split())
MOD = 10**9 + 7

U = [0]
V = []
for x in range(1, int(N**.5)+1):
    U.append(x)
    if x < N//x:
        V.append(N//x)
V.reverse()
U.extend(V)

L = len(U)
memo = {(K, e): 1 for e in U}
for k in range(K-1, -1, -1):
    memo[k, 0] = 0
    r = 0
    for x, y in zip(U, U[1:]):
        memo[k, y] = r = ((y - x) * memo[k+1, N//y] + r) % MOD
print(memo[0, N])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N, K = map(int, input().split())
MOD = 10**9 + 7

U = [0]; V = []
for x in range(1, int(N**.5)+1):
    U.append(x)
    if x < N//x:
        V.append(N//x)
V.reverse(); U.extend(V)

L = len(U)
S = [1]*L
S[0] = 0
for k in range(K-1, -1, -1):
    T = [0]*L
    r = 0
    for i in range(1, L):
        x = U[i-1]; y = U[i]
        T[i] = r = ((y - x) * S[L-i] + r) % MOD
    S = T
print(S[-1])