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

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(v, graph, seen, next_v, rank):
    for x in graph[v]:
        if x in seen:
            continue
        next_v.append(x)
        rank.append(rank[0]+1)

next_v = [0]
rank = [0]
seen = [0]
#bfs
while True:
    if len(next_v) == 0 or rank[0] == 3:
        ans = "IMPOSSIBLE"
        break
    if next_v[0] == N-1:
        ans = "POSSIBLE"
        break
    bfs(next_v[0], graph, seen, next_v, rank)
    next_v.pop(0)
    rank.pop(0)
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
graph = [[] for _ in range(N)] 
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(goal, graph, seen, next_v):
    for x in graph[next_v[0][0]]:
        if x == goal:
            return True
        if x in seen:
            continue
        next_v.append((x,next_v[0][1]+1))
        seen.add(x)
    return False


next_v = [(0,0)]
seen = {0}
#bfs
while True:
    if len(next_v) == 0 or next_v[0][1] == 2:
        ans = "IMPOSSIBLE"
        break
    if bfs(N-1, graph, seen, next_v):
        ans = "POSSIBLE"
        break
    next_v.pop(0)
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

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

k = int(input())
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans += gcd(a,b,c)
print(ans)

### FIXED CODE ###

import math
from functools import reduce

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

k = int(input())
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans += gcd(a,b,c)
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
n, m = [int(i) for i in sys.stdin.readline().split()]
dis_dict = dict()
parent = [i for i in range(n)]

def find_root(a):
    ls = []
    while parent[a] != a:
        ls.append(a)
        a = parent[a]
    for l in ls:
        parent[l] = a
    return a

def is_same(a, b):
    root_a = find_root(a)
    root_b = find_root(b)
    return root_b == root_a

def unite(a, b):
    root_a = find_root(a)
    root_b = find_root(b)
    if root_a != root_b:
        parent[root_b] = root_a

graph = {j:[] for j in range(n)}
for i in range(m):
    l, r, d = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    unite(l, r)
    graph[l].append((r, d))
    graph[r].append((l, -d))

roots = [find_root(i) for i in range(n)]
x_ls = [None if i not in roots else 0 for i in range(n)]
que = deque(list(set(roots)))
flg = True
while len(que) > 0:
    cur = que.popleft()
    cur_pos = x_ls[cur]
    for _next, dis in graph[cur]:
        if x_ls[_next] is None:
            x_ls[_next] = cur_pos + dis
            que.append(_next)
        else:
            if x_ls[_next] != cur_pos + dis:
                flg = False
                break
    if not flg:
        break
if flg:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

graph = {j:[] for j in range(n)}
for i in range(m):
    l, r, d = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    graph[l].append((r, d))
    graph[r].append((l, -d))

already = set()
x_ls = [None for i in range(n)]
x_ls[0] = 0
stack = list(range(n))[::-1]
flg = True
while len(stack) > 0:
    cur = stack.pop(-1)
    if cur in already:
        continue
    if x_ls[cur] is None:
        cur_pos = 0
    else:
        cur_pos = x_ls[cur]
    already.add(cur)
    for _next, dis in graph[cur]:
        if x_ls[_next] is None:
            x_ls[_next] = cur_pos + dis
            stack.append(_next)
        else:
            if x_ls[_next] != cur_pos + dis:
                flg = False
                break
    if not flg:
        break
if flg:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

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

sum_A = [0]
for  i in range(N):
    sum_A.append(sum_A[i] + A[i])

sum_B = [0]
for  i in range(M):
    sum_B.append(sum_B[i] + B[i])

ans = 0
s = 0

for i in range (N + 1):
    for j in range(M + 1):
        s = sum_A[i] + sum_B[j]
        if s <= K:
            ans = max(ans, i + j)
        else:
            break

print(ans)


### FIXED CODE ###

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

sum_A = [0]
for  i in range(N):
    sum_A.append(sum_A[i] + A[i])

sum_B = [0]
for  i in range(M):
    sum_B.append(sum_B[i] + B[i])

ans = 0
j = M

for i in range (N+1):
    if sum_A[i] > K:
        break
    while sum_B[j] > K - sum_A[i]:
        j -= 1
    ans = max(ans, i+j)

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

N, Q =map(int,input().split())
S =input()
LR = [list(map(int,input().split())) for i in range(Q)]
isACinit =[0]*N
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        isACinit[i] = 1
#ans = [0]*Q
#print(isACinit)
ACsum = sum(isACinit)
for i in range(Q):
    if LR[i][1]-LR[i][0]>N//2:
        print(sum(isACinit[LR[i][0]-1:LR[i][1]-1]))
    else:
        print(ACsum-sum(isACinit[:LR[i][0]-1])-sum(isACinit[LR[i][1]-1:]))

### FIXED CODE ###

N, Q =map(int,input().split())
S =input()
LR = [list(map(int,input().split())) for i in range(Q)]
ACnum =[0]*(N+1)
Sofar = 0
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        Sofar+=1
    ACnum[i+1] = Sofar
ACnum[N]=Sofar
#print(ACnum)
for i in range(Q):
    print(ACnum[LR[i][1]-1]-ACnum[LR[i][0]-1])
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

from itertools import product
D=sorted([a+b for a,b in product(A,B)],reverse=True)
D=D[:K]
E=sorted([d+c for d,c in product(D,C)],reverse=True)
for i in range(K):
    print(E[i])


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
C=C[:K]

from itertools import product
D=sorted([a+b for a,b in product(A,B)],reverse=True)
D=D[:K]
E=sorted([d+c for d,c in product(D,C)],reverse=True)
E=E[:K]
for i in range(K):
    print(E[i])
### BUGGY CODE ###

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


INF = 10**9


def BellmanFord(edges, num_v, source):
      # グラフの初期化
    inf = float("inf")
    dist = [inf for i in range(num_v)]
    dist[source-1] = 0

    # 辺の緩和
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i == num_v-1:
                    return -1

    return dist


edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a-1, b-1, 1))
    edges.append((b-1, a-1, 1))


if BellmanFord(edges, n, 0)[-2] < 3:
    print('POSSIBLE')
    exit(0)
print('IMPOSSIBLE')


### FIXED CODE ###

# ABC068c
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
INF = 10**12


class Edge:  # 通常の辺
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


class Dijkstra:  # ダイクストラ法 O(E * logV)
    def __init__(self, n):
        self.n = n
        self.dist = [INF for _ in range(n)]
        self.edges = [list() for _ in range(n)]
        self.q = collections.deque()

    def calcShortest(self, start):
        self.q.append((start, 0))
        while(len(self.q) != 0):
            v, cost = self.q.popleft()
            if cost > 3:
                continue
            if self.dist[v] <= cost:
                continue
            self.dist[v] = cost
            for edge in self.edges[v]:
                self.q.append((edge.to, cost+edge.cost))

    def addEdge(self, st, gl, cost):
        self.edges[st].append(Edge(gl, cost))


v = Dijkstra(n)
for _ in range(m):
    a, b = map(int, input().split())
    v.addEdge(a-1, b-1, 1)
    v.addEdge(b-1, a-1, 1)

v.calcShortest(0)
if v.dist[n-1] <= 2:
    print('POSSIBLE')
    exit(0)
print('IMPOSSIBLE')
### BUGGY CODE ###

from collections import deque

s = input()
d = deque()
for i in s:
    d.append(i)
q = int(input())
for i in range(q):
        data = input().split()
        if len(data) == 1:
            if len(d) != 1:
                d.reverse()
        else:
            f = int(data[1])
            c = data[2]
            if f == 1:
                d.appendleft(c)
            else:
                d.append(c)
s = list(d)
s = "".join(s)
print(s)

### FIXED CODE ###

from collections import deque

s = input()
d = deque()
header = 1
for i in s:
    d.append(i)
q = int(input())
for i in range(q):
        data = input().split()
        if len(data) == 1 :
            header *= -1
        else:
            f = int(data[1])
            c = data[2]
            if header == 1:
                if f == 1:
                    d.appendleft(c)
                else:
                    d.append(c)
            else:
                if f == 1:
                    d.append(c)
                else:
                    d.appendleft(c)
                
if header == -1:
    d.reverse()

s = list(d)
s = "".join(s)



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

n,m = map(int,input().split())
l = list(map(int,input().split()))
l.sort()
for i in range(m):
    a,b = map(int,input().split())
    for i in range(a):
        if l[i] < b:
            l[i] = b
    l.sort()
print(sum(l))


### FIXED CODE ###

n,m = map(int,input().split())
l = list(map(int,input().split()))
l.sort()
check = []
for i in range(m):
    a,b = map(int,input().split())
    check.append([a,b])
check.sort(key =  lambda x: x[1],reverse=True)

count = 0
for a,b in check:
    for j in range(a):
        if l[count] < b:
            l[count] = b
        count += 1
        
        if count == n:
            print(sum(l))
            exit()
print(sum(l))
### BUGGY CODE ###

N = int(input())
S = input()
counter = {'R':0, 'G':0, 'B':0}
for s in S:
    counter[s] += 1

ans = counter['R'] * counter['G'] * counter['B']
for i in range(N):
    for j in range(i + 1, N):
        if S[i] != S[j] and 2 * j - i < N and S[i] != S[2 * j - i] and S[j] != S[2 * j - i]:
            ans -= 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
counter = {'R':0, 'G':0, 'B':0}
for s in S:
    counter[s] += 1

ans = counter['R'] * counter['G'] * counter['B']
for i in range(N):
    for j in range(i + 1, N):
        if S[i] != S[j] and 2 * j - i < N and S[i] != S[2 * j - i] and S[j] != S[2 * j - i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

# 2019/08/11

from fractions import gcd

n,m=map(int,input().split())
s=list(input())
t=list(input())
lcd=(n*m)//gcd(n,m)
x=['' for _ in range(lcd)]

for i in range(n):
    a=i*(lcd//n)
    x[a]=s[i]

for i in range(m):
    b=i*(lcd//m)
    if x[b]==t[i] or x[b]=='':
        x[b]=t[i]
    else:
        print(-1)
        exit()
    
print(lcd)


### FIXED CODE ###

# 2019/08/11

from fractions import gcd

n,m=map(int,input().split())
s=input()
t=input()
lcd=(n*m)//gcd(n,m)
x={}
aa=(lcd//n)
bb=(lcd//m)
for i in range(n):
    a=i*aa
    x[a]=s[i]

for i in range(m):
    b=i*bb
    if b in x and x[b]!=t[i]:
        print(-1)
        exit()
    
print(lcd)
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(graph: list, node: int, start: int) -> list:
    # graph[node] = [(cost, to)]
    inf = 3 * 10 ** 9
    dist = [inf] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]

xs, ys, xt, yt = map(int, input().split())
n = int(input())
circles = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
    circles.append(tuple(map(int, input().split())))
n += 2

edges = [[] for i in range(n)]
for i in range(n):
    for j in range(i+1, n):
        dist = ((circles[i][0] - circles[j][0]) ** 2 + (circles[i][1] - circles[j][1]) ** 2) ** 0.5
        cost = max(0, dist - circles[i][2] - circles[j][2])
        edges[i].append((cost, j))
        edges[j].append((cost, i))


dist = dijkstra(edges, n, 0)

print(dist[1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

def dijkstra(edge_adj: list, node: int, start: int) -> list:
    # graph[node] = [(cost, to)]
    inf = 3 * 10 ** 9
    dist = [inf] * node
    used = [False] * node

    dist[start] = 0
    while True:
        v = -1
        for i in range(node):
            if not used[i] and (v == -1 or dist[v] > dist[i]):
                v = i

        if v == -1:
            break

        used[v] = True
        for i in range(node):
            if dist[i] > dist[v] + edge_adj[v][i]:
                dist[i] = dist[v] + edge_adj[v][i]

    return dist
    # dist = [costs to nodes]

xs, ys, xt, yt = map(int, input().split())
n = int(input())
circles = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
    circles.append(tuple(map(int, input().split())))
n += 2

edges = [[0] * n for i in range(n)]
for i in range(n):
    for j in range(i+1, n):
        dist = ((circles[i][0] - circles[j][0]) ** 2 + (circles[i][1] - circles[j][1]) ** 2) ** 0.5
        cost = max(0, dist - circles[i][2] - circles[j][2])
        edges[i][j] = cost
        edges[j][i] = cost


dist = dijkstra(edges, n, 0)

print(dist[1])
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())

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

C.sort(reverse=True)
tmp = []
ans = []

for i in range(X):
	for j in range(Y):
		tmp.append(A[i]+B[j])
tmp.sort(reverse=True)

for i in range(min(X*Y, K)):
	for j in range(min(Z, K)):
		ans.append(tmp[i]+C[j])

ans.sort(reverse=True)

for i in range(min(K, X*Y*Z)):
	print(ans[i])


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())

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

C.sort(reverse=True)
tmp = []
ans = []

for i in range(X):
	for j in range(Y):
		tmp.append(A[i]+B[j])

tmp.sort(reverse=True)
del tmp[min(K, X*Y):]

for i in range(len(tmp)):
	for j in range(min(Z, K)):
		ans.append(tmp[i]+C[j])

ans.sort(reverse=True)

for i in range(min(K, X*Y*Z)):
	print(ans[i])
### 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 idx_c in range(N):
  idx_b = bisect.bisect_left(B,C[idx_c])
  if idx_b == 0: continue
  for i in range(idx_b):
    idx_a = bisect.bisect_left(A,B[i])
    if idx_a == 0: continue
    ans += idx_a
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()
C.sort()

ans = 0
mem_idx_a = {}
for idx_b in range(N):
  idx_c = bisect.bisect_right(C,B[idx_b])
  idx_a = bisect.bisect_left(A,B[idx_b])
  ans += (N-idx_c)*idx_a
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import heapq
from collections import deque
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# A=(tuple(input()) for i in range(h))
# print(A)
dis=[[-1]*w for i in range(h)]
hq=deque()
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
# heapq.heapify(hq)
ans=0
while hq:
    count,i,j=hq.popleft()
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            hq.append((count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)
#             # print(count+1)
# ans=0
# for Ai in dis:
#     ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)

    
    


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq
from collections import deque
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# A=(tuple(input()) for i in range(h))
# print(A)
dis=[[-1]*w for i in range(h)]
hq=deque()
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
# heapq.heapify(hq)
ans=0
while hq:
    count,i,j=hq.popleft()
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            hq.append((count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)
#             # print(count+1)
# ans=0
# for Ai in dis:
#     ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)
### BUGGY CODE ###

import sys

N,K=list(map(int,input().split()))
h=list(map(int,input().split()))

dp=[sys.maxsize]*100100
dp[1]=0

for i in range(1,N):
    if i<K:
        for k in range(i):dp[i+1]=min(dp[i+1],dp[i-k]+abs(h[i]-h[i-1-k]))
    else:
        for k in range(K):dp[i+1]=min(dp[i+1],dp[i-k]+abs(h[i]-h[i-1-k]))

print(dp[N])

        
    


### FIXED CODE ###

import sys
import numpy as np
# inputを高速化する。
input = sys.stdin.readline
n, k = map(int, input().split())
h = [int(i) for i in input().split()]
# dpの配列を作る。
dp = np.zeros(n, dtype=int)
# hの配列を作る。
h = np.array(h)
for i in range(1, n):
    # start は負になることはない。
    start = max(0, i-k)
    # 行列として足し算できるのでforを使う必要がない。
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))
print(dp[n-1])
### BUGGY CODE ###

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

# import bisect

L.sort()
# print(L)

ans = 0
for l1ix in range(N-1, -1, -1):
    for l2ix in range(l1ix - 1, -1, -1):
        # binsearch
        l = -1
        r = l2ix + 1

        while (r - l) > 1:
            mid = l + (r - l) // 2

            if L[mid] < (L[l1ix] + L[l2ix]) and L[l2ix] < L[mid] + L[l1ix] and L[l1ix] < L[mid] + L[l2ix]:
                #ok
                r = mid
            else:
                #ng
                l = mid
        
        l3ix = r
        # if l2ix != l3ix:
        #     print("1,2,3=", L[l1ix], L[l2ix], L[l3ix])
        
        anst = l2ix - l3ix
        ans += anst if anst > 0 else 0

print(ans)
        


"""
O(N^3)だから間に合わない．明らかに間に合うアルゴリズムを探す
ans = 0
for aix in range(N):
    for bix in range(aix + 1, N):
        for cix in range(bix + 1, N):
            if L[aix] < L[bix] + L[cix] and L[bix] < L[aix] + L[cix] and L[cix] < L[aix] + L[bix]:
                # print("ok:", aix,",", bix,",", cix)
                ans += 1

print(ans)
"""


### FIXED CODE ###

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

import bisect

L.sort()
# print(L)

ans = 0
for i in range(0, N-1):
    for j in range(i+1, N-1):
        ix = bisect.bisect_left(L, L[i] + L[j])
        ans += max(0, ix - j - 1)

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

n = int(input())
nums = []
for i in range(n):
  num = int(input())
  nums.append(num)
count = 0
setnums = set(nums)
for j in setnums:
  test = nums.count(j)
  if test % 2 == 1:
    count += 1
print(count)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
nums = []
for i in range(n):
  num = int(input())
  nums.append(num)
d = defaultdict(int)
for j in nums:
  d[j] += 1
count = 0
for k in d.values():
  if k % 2 == 1:
    count += 1
print(count)
### BUGGY CODE ###

from collections import defaultdict
from fractions import Fraction
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 1 に至ったら終了
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in range(N):
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  if Fraction(A,B)>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[-1/Fraction(A,B)][1]+=1
ans=1
for k in dic:
 ans*=(powmod(2,dic[k][0],mod)+powmod(2,dic[k][1],mod) -1)
 ans%=mod
ans*=(powmod(2,c,mod)+powmod(2,d,mod)-1)
print((ans-1+e)%mod)

### FIXED CODE ###

from collections import defaultdict
from math import gcd
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  g=gcd(A,B)
  A//=g
  B//=g
  if A*B>0:
   dic[(abs(A),abs(B))][0]+=1
  else:
   dic[(abs(B),abs(A))][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)
### BUGGY CODE ###

import bisect
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
a.sort()
b.sort()
b=b[::-1]
c.sort()
ans=tmp=0
for i in a:
    for j in b:
        if i>=j: break
        tmp=bisect.bisect_right(c, j)
        ans+=(n-tmp)
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
a.sort()
b.sort()
b=b[::-1]
c.sort()
ans=tmp=0
for i in b:
    x=bisect.bisect_left(a,i)
    y=bisect.bisect_right(c, i)
    ans+=x*(n-y)
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())
S_l = len(S)
ans = 0
from collections import deque
R = deque([])
G = deque([])
B  = deque([])
for i,s in enumerate(S):
    if s=='R':
        R.append(i)
    elif s=='G':
        G.append(i)
    elif s=='B':
        B.append(i)

def res(X,Y,S,i,a,b):
  x = X.copy()
  ret = 0
  for y in Y:
    if len(x)!=0:
      while x[0]<y:
        x.popleft()
        if len(x)==0:
          break
    ret+=len(x)
    tmp = 2*y-i
    if tmp>=S_l:
      continue
    if S[tmp]==a:
      ret-=1
  
  y = Y.copy()
  for x in X:
    if len(y)!=0:
      while y[0]<x:
        y.popleft()
        if len(y)==0:
          break
    ret+=len(y)
    tmp = 2*x-i
    if tmp>=S_l:
      continue
    if S[tmp]==b:
      ret-=1

      
  return ret
    
for i in range(len(S)):
    if S[i]=='R':
      r = R.popleft()
      ans += res(G,B,S,i,'G','B')
    elif S[i]=='G':
      g = G.popleft()
      ans += res(R,B,S,i,'R','B')
    else:
      b = B.popleft()
      ans += res(R,G,S,i,'R','G')
      
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
S_l = len(S)
ans = 0
from collections import deque
R = deque([])
G = deque([])
B  = deque([])
for i,s in enumerate(S):
    if s=='R':
        R.append(i)
    elif s=='G':
        G.append(i)
    elif s=='B':
        B.append(i)

def res(X,Y,S,i,a,b):
  x = X.copy()
  ret = 0
  for y in Y:
    if len(x)!=0:
      while x[0]<y:
        x.popleft()
        if len(x)==0:
          break
    ret+=len(x)
    tmp = 2*y-i
    if tmp>=S_l:
      continue
    if S[tmp]==a:
      ret-=1
  
  y = Y.copy()
  for x in X:
    if len(y)!=0:
      while y[0]<x:
        y.popleft()
        if len(y)==0:
          break
    ret+=len(y)
    tmp = 2*x-i
    if tmp>=S_l:
      continue
    if S[tmp]==b:
      ret-=1

      
  return ret
    
for i in range(len(S)):
    if S[i]=='R':
      r = R.popleft()
      ans += res(G,B,S,i,'G','B')
    elif S[i]=='G':
      g = G.popleft()
      ans += res(R,B,S,i,'R','B')
    else:
      b = B.popleft()
      ans += res(R,G,S,i,'R','G')
      
print(ans)