Harryxun/stf_run huggingface dataset:
A,B=map(int,input().split())

def get_cd(x1,x2):
    cd=[]
    for i in range(1,min(x1,x2)+1):
        if x1%i==0 and x2%i==0:
            cd.append(i)
    return cd

cd_AB=get_cd(A,B)

for j in range (0,len(cd_AB)-1):
    for k in range(j+1,len(cd_AB)):
            if(len(get_cd(cd_AB[j],cd_AB[k]))>1):
            cd_AB[k]=0

print(len(cd_AB)-cd_AB.count(0))

### FIXED CODE ###

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        count=0
        while n % b == 0:
            n //= b
            count+=1
            if(count==1):
                fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

A,B=map(int,input().split())
g=gcd(A,B)
if(g==1):
    print("1")
else:
    print(len(factorize(g))+1)
a = input().split()
ans = []
for i in a:
  if a == "1":
    ans.append("9")
  elif a == "9":
    ans.append("1")
  else:
    ans.append(a)
print("".join(ans))

### FIXED CODE ###

a = list(input())
ans = []
for i in a:
  if i == "1":
    ans.append("9")
  elif i == "9":
    ans.append("1")
  else:
    ans.append(i)
print(''.join(ans))
import sys
s = sys.stdin.readlines()

s = s[0]
q = int(s[1]) #int(input())
inv = 1

for t in s[2:q+1]:
  # t = input()
  if t[0] == '1':
    inv *= -1 #s = s[::-1]
  else:
    _, f, c = map(str, t.split())
    if (f =='1' and inv == 1) or (f =='2' and inv == -1):
      s = c+s
    else:
      s = s+c

print(s[::inv])

### FIXED CODE ###

s = list(input())
q = int(input()) #int(input())
inv = 1
query = [input() for _ in range(q)]
bef = []
aft = []


for t in query:
  if t == '1':
    inv *= -1 #s = s[::-1]
  else:
    _, f, c = map(str, t.split())
    if (f =='1' and inv == 1) or (f =='2' and inv == -1):
      # s = c+s
      bef.append(c)
    else:
      # s = s+c
      aft.append(c)

bef.reverse()
bef.extend(s)
bef.extend(aft)

print(''.join(bef[::inv]))
blist.sort()
# 偶数の場合
if N % 2 == 0:
    median1 = N/2
    median2 = N/2 + 1
    median1 = int(median1) - 1
    median2 = int(median2) - 1
    amedian = (alist[median1] + alist[median2]) / 2
    bmedian = (blist[median1] + blist[median2]) / 2
    print(bmedian-amedian+1)
# 奇数の場合
else:
    median = (N + 1) / 2
    median = int(median) - 1
    amedian = alist[median]
    bmedian = blist[median]
    print((bmedian-amedian)*2+1)


### FIXED CODE ###

n = int(input())
alist = []
blist = []
for i in range(n):
    a,b = map(int,input().split())
    alist.append(a)
    blist.append(b)

N = len(alist)
alist.sort()
blist.sort()
# 偶数の場合
if N % 2 == 0:
    median1 = N/2
    median2 = N/2 + 1
    median1 = int(median1) - 1
    median2 = int(median2) - 1
    amedian = (alist[median1] + alist[median2]) / 2
    bmedian = (blist[median1] + blist[median2]) / 2
    ans = (bmedian-amedian)*2+1
# 奇数の場合
else:
    median = (N + 1) / 2
    median = int(median) - 1
    amedian = alist[median]
    bmedian = blist[median]
    ans = bmedian-amedian+1
print(int(ans))
N,M,P = map(int,input().split())
edges = []
L = [[] for i in range(N)]
utov = [[] for i in range(N)]
vtou = [[] for i in range(N)]

for i in range(M) :
    u,v,cost = map(int,input().split())
    u -= 1
    v -= 1
    cost -= P
    cost *= -1
    edges.append([u,v,cost])
    utov[u].append(v)
    vtou[v].append(u)

reachableFromS = [False]*N
reachableFromG = [False]*N

def dfs(u) :
    if reachableFromS[u] :
        return
    reachableFromS[u] = True
    for v in utov[u] :
        dfs(v)

def dfs2(v) :
    if reachableFromG[v] :
        return
    reachableFromG[v] = True
    for u in vtou[v] :
        dfs2(u)

dfs(0)
dfs2(N-1)

OK = [reachableFromS[i] * reachableFromG[i] for i in range(N)]

dist = [float("inf")]*N
dist[0] = 0

ans = 0
step = 0
update = True

while update :
    update = False
    for i in range(M) :
        u,v,cost = edges[i]
        if OK[u] * OK[v] == 0 :
            continue
        if dist[v] > dist[u] + cost :
            dist[v] = dist[u] + cost
            update = True
    
    step += 1
    if step > N :
        ans = -1
        break

if ans != -1 :
    ans = max(0, dist[N-1] * (-1))
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N,M,P = map(int,input().split())
edges = []
L = [[] for i in range(N)]
utov = [[] for i in range(N)]
vtou = [[] for i in range(N)]

for i in range(M) :
    u,v,cost = map(int,input().split())
    u -= 1
    v -= 1
    cost -= P
    cost *= -1
    edges.append([u,v,cost])
    utov[u].append(v)
    vtou[v].append(u)

reachableFromS = [False]*N
reachableFromG = [False]*N

def dfs(u) :
    if reachableFromS[u] :
        return
    reachableFromS[u] = True
    for v in utov[u] :
        dfs(v)

def dfs2(v) :
    if reachableFromG[v] :
        return
    reachableFromG[v] = True
    for u in vtou[v] :
        dfs2(u)

dfs(0)
dfs2(N-1)

OK = [reachableFromS[i] * reachableFromG[i] for i in range(N)]

dist = [float("inf")]*N
dist[0] = 0

ans = 0
step = 0
update = True

while update :
    update = False
    for i in range(M) :
        u,v,cost = edges[i]
        if OK[u] * OK[v] == 0 :
            continue
        if dist[v] > dist[u] + cost :
            dist[v] = dist[u] + cost
            update = True
    
    step += 1
    if step > N :
        ans = -1
        break

if ans != -1 :
    ans = max(0, dist[N-1] * (-1))
print(ans)
N=map(int, input())
list=list(map(str, input().split()))
answer={}
for i in range(1, N+1):
	m=0
	for j in range(0, len(list)):
  		if list[j] is str(i):
      		m=m+1
    	else:
      		m=m+0
	answer.append(m)
a_s='\n'.join(answer)
print(a_s)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
ans=[0]*N
for a in A:
  ans[a-1]+=1
for n in ans:
  print(n)
N = int(input())
S = [input() for _ in range(N)]

# 文字列にABが入ってる数 + 組み合わせて入る数
# 文字列にABが入ってる数 + f(Aで終わる数, Bで始まる数, Bで始まりAで終わる数)
include = 0
sb = 0
fa = 0
sbfa = 0
for s in S:
    if 'AB' in s:
        include += 1
    if s[0] == 'B' and s[-1] == 'A':
        sbfa += 1
    elif s[0] == 'B':
        sb += 1
    elif s[-1] == 'A':
        fa += 1

def calc_comb(sb, fa, sbfa):
    ans = 0
    if sbfa > 0:
        ans += sbfa-1
        if sb > 0:
            sb -= 1
            ans += 1
        if fa > 0:
            fa -= 1
            ans += 1
    ans += min(sb, fa)

print(include + calc_comb(sb, fa, sbfa))


### FIXED CODE ###

n = int(input())
s_array = [input() for x in range(n)]
a_count = 0
b_count = 0
ab_count = 0
for s in s_array:
    if s[-1] == "A" and s[0] != "B":
        a_count += 1
    elif s[0] == "B" and s[-1] != "A":
        b_count += 1
    elif s[0] == "B" and s[-1] == "A":
        ab_count += 1
    else:
        pass

res = sum([x.count("AB") for x in s_array])

if n == 1:
    print(res)
elif ab_count == 0:
    print(res + min(a_count, b_count))
elif a_count == 0 and b_count == 0:
    print(res - 1 + ab_count)
else:
    print(res + min(a_count, b_count) + ab_count)
N=input()

def yomikata(N):
    N_firstdigit=N%10
    if N_firstdigit==3:
        print("bon")
    #elif N_firstdigit==0 or 1 or 6 or 8: このように条件は省略して書いてはだめらしい!
    elif N_firstdigit==0 or N_firstdigit==1 or N_firstdigit==6 or N_firstdigit==8:
        print("pon")
    else:
        print("hon")
        
yomikata(N)

### FIXED CODE ###

N=int(input())

def yomikata(N):
    N_firstdigit=N%10
    if N_firstdigit==3:
        print("bon")
    #elif N_firstdigit==0 or 1 or 6 or 8: このように条件は省略して書いてはだめらしい!
    elif N_firstdigit==0 or N_firstdigit==1 or N_firstdigit==6 or N_firstdigit==8:
        print("pon")
    else:
        print("hon")
        
yomikata(N)
import sys
import itertools

cols = []
for line in sys.stdin:
  col = line.strip().split(' ')
  col = [int(c) for c in col]
  cols.append(col)

def calcH(cx, cy, x, y, h):
  if h > 0:
  	return h + abs(x-cx) + abs(y-cy)
  else:
    return h - abs(x-cs) - abs(y-cy) <= 0

cols = cols[1:]
for cx,cy in itertools.product(list(range(101)), list(range(101))):
  H = None
  flag = True
  for x,y,h in cols:
    now_H = calcH(cx, cy, x, y, h)
    if not H:
      flag = False
      break
    if H is None:
      H = now_H
    else:
      if not H == now_H:
        flag = False
        break
  if flag:
    print(cx,cy,H)


### FIXED CODE ###

import sys
import itertools

cols = []
for line in sys.stdin:
  col = line.strip().split(' ')
  col = [int(c) for c in col]
  cols.append(col)

cols = cols[1:]
for cx,cy in itertools.product(list(range(101)), list(range(101))):
  H, H_max, flag = None, None, True
  for x,y,h in cols:
    if h <= 0:
      tmp_H_max = abs(x-cx) + abs(y-cy)
      if tmp_H_max < 1:
        flag = False
        break
      else:
        H_max = min(H_max, tmp_H_max) if H_max else tmp_H_max
      if H and H_max < H:
        flag = False
        break
    else:
      tmp_H = h + abs(x-cx) + abs(y-cy)
      if not H:
        H = tmp_H
      elif H and H != tmp_H:
        flag = False
        break
      if H_max and H_max < tmp_H:
        flag = False
        break
  if flag:
    print(cx,cy,H)
s = input()
k = int(input())

for i in range(len(s)):
    if int(s[i]) != 1:
        ans = int(s[i])
        break
        
print(ans)

### FIXED CODE ###

s = input()
k = int(input())

import numpy as np

ind = np.inf

for i in range(len(s)):
    if int(s[i]) != 1:
        ind = i
        ans = int(s[i])
        break
if ind >= k:
    ans = 1
    
print(ans)
#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
C = readline().decode().rstrip()

w_idx = []
r_idx = []
for i, c in enumerate(C):
    if c == 'W':
        w_idx.append(i)
    else:
        r_idx.append(i)

m = r_idx[len(r_idx) // 2 - 1]

if (len(w_idx) == 0) | (len(r_idx) == 0):
    print(0)
    sys.exit()

cnt = 0
for w in w_idx:
    if w < m:
        cnt += 1

print(cnt)

### FIXED CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
C = readline().decode().rstrip()

l, r = 0, N - 1
cnt = 0

while l < r:
    if C[l] == 'R':
        l += 1
    elif C[r] == 'W':
        r -= 1
    else:
        l += 1
        r -= 1
        cnt += 1

print(cnt)
while True:
    x,y = map(int, input().split())
    if x == y == 0:
        continue
    if x => y:
        print (y,x)
    else:
        print (x,y)

### FIXED CODE ###

while True:
    x,y = map(int, input().split())
    if x == 0 and y == 0 :
        break
    elif x <= y :
        print (x,y)
    else :
        print (y,x)
from collections import Counter

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

cnt = Counter(A)

if cnt[0] == N:
    print("Yes")
else:
    if N % 3 != 0:
        print("No")
    else:
        if cnt.most_common(1)[0][1] == N*2//3 and cnt[0] == N//3:
            print("Yes")
        else:
            x = cnt.most_common(3)
            if x[0][1] == x[1][1] == x[2][1]:
                if x[0][0]^x[1][0]^x[2][0] == 0:
                    print("Yes")
                else:
                    print("No")
            else:
                print("No")

### FIXED CODE ###

from collections import Counter

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

cnt = Counter(A)

try:
    if cnt[0] == N:
        print("Yes")
    else:
        if N % 3 != 0:
            print("No")
        else:
            if cnt.most_common(1)[0][1] == N*2//3 and cnt[0] == N//3:
                print("Yes")
            else:
                x = cnt.most_common(3)
                if x[0][1] == x[1][1] == x[2][1] == N//3:
                    if x[0][0]^x[1][0]^x[2][0] == 0:
                        print("Yes")
                    else:
                        print("No")
                else:
                    print("No")
except:
    print("No")
N=int(input())
A=list(map(int, input().split()))
n=0
while all(a%2==0 for a in A):
    A=[a/2 for a in A]
    n+=1
print(n)

### FIXED CODE ###

print(input().count('1'))
import heapq

N,M = map(int,input().split())

A = [int(i)*-1 for i in input().split()]
heapq.heapify(A)

for _ in range(M):
  max = heapq.heappop(A) * -1
  heapq.heappush(A,(max//2)*-1)





print(sum(A)*-1)  




### FIXED CODE ###

N=input()
a=''
if N[0] =='S':
  a='Cloudy'
elif N[0] =='C':
  a='Rainy'
else:
  a='Sunny'

print(a)
# -*- coding: utf-8 -*-


def main():
    n, x = map(int, input().split())
    lst = [input() for i in range(n)]
    print(n, x)
    print(lst)

    d = []
    for i in range(n + 1):
        if i == 0:
            d.append(0)
        else:
            d.append(d[i - 1] + int(lst[i - 1]))
    print(d)

    bound = 0

    for n, i in enumerate(d):
        if i <= x:
            bound += 1
        else:
            break
    print(bound)


if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    n, x = map(int, input().split())
    lst = list(map(int,input().split()))
    lst = lst[:n]

    d = []
    for i in range(n + 1):
        if i == 0:
            d.append(0)
        else:
            d.append(d[i - 1] + int(lst[i - 1]))

    bound = 0

    for n, i in enumerate(d):
        if i <= x:
            bound += 1
        else:
            break
    print(bound)


if __name__ == '__main__':
    main()
import networkx as nx

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

S = [list(input()) for _ in range(n)]
G = nx.DiGraph()

start = (n, m)
cnt = 0
goal = (n, m + 1)

for i in range(n):
    for j in range(n):
        if S[i][j] != "#":
            if S[i][j] == "o":
                cnt += 1
                G.add_edge(start, (i, j), capacity=1)
            if i + 1 < n:
                if S[i + 1][j] != "#":
                    G.add_edge((i, j), (i + 1, j), weight=-1)
            if j + 1 < m:
                if S[i][j + 1] != "#":
                    G.add_edge((i, j), (i, j + 1), weight=-1)
            G.add_edge((i, j), goal, capacity=1)
# G.add_node(start, demand=cnt)
# G.add_node(goal, demand=-cnt)
mincostflow = nx.max_flow_min_cost(G, start, goal)
ans = nx.cost_of_flow(G, mincostflow)
print(abs(ans))


### FIXED CODE ###

import networkx as nx

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

S = [list(input()) for _ in range(n)]
G = nx.DiGraph()

start = (n, m)
cnt = 0
goal = (n, m + 1)

for i in range(n):
    for j in range(m):
        if S[i][j] != "#":
            if S[i][j] == "o":
                cnt += 1
                G.add_edge(start, (i, j), capacity=1)
            if i + 1 < n:
                if S[i + 1][j] != "#":
                    G.add_edge((i, j), (i + 1, j), weight=-1)
            if j + 1 < m:
                if S[i][j + 1] != "#":
                    G.add_edge((i, j), (i, j + 1), weight=-1)
            G.add_edge((i, j), goal, capacity=1)
# G.add_node(start, demand=cnt)
# G.add_node(goal, demand=-cnt)
mincostflow = nx.max_flow_min_cost(G, start, goal)
ans = nx.cost_of_flow(G, mincostflow)
print(abs(ans))
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

M = 998244353
B = pow(10, 18, M)
N = int(input())

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
  prev_i = 1
  prev_W = B
  for i in range(1, N+1):
    if i in g:
      W = (B * pow(B, prev_i-i, M)) % M
      sum_g[g[i]] = (sum_g[g[i]] + W) % M
      sum_g[0]  = (sum_g[0] - W) % M
      prev_i, prev_W = i, W
  
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = (ret + sx*sy*sz) % M
  return ret

edge = [read_edge() for i in range(3)]

print(solve(N, edge))

### FIXED CODE ###

from collections import defaultdict

M = 998244353
B = 10**18 % M

def mex(s):
  for i in range(max(s)+2):
    if i not in s:
      return i

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in sorted(e.keys(), reverse=True):
    m = mex({g.get(j,0) for j in e[i]})
    if m:
      g[i] = m
      x = pow(B, i, M)
      sum_g[m] += x
      sum_g[0] -= x
  return sum_g

def get_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, x in sum_g[0].items():
    for gy, y in sum_g[1].items():
      gz = gx^gy
      z = sum_g[2][gz]
      ret = (ret + x*y*z)%M
  return ret

N = int(input())
edge = [get_edge() for i in range(3)]

print(solve(N, edge))
price = list(map(int, input().rstrip().split()))
print(min(price[0]*price[1], price[2])

### FIXED CODE ###

price = list(map(int, input().rstrip().split()))
print(min(price[0]*price[1], price[2]))
n,m= map(int,input().split())
inputs = []
for _ in range(m):
    inputs.append(list(map(int,input().split())))

if m == 0:
    print(10**(n-1))
    exit()
elif n == 1:
    if len([i[1] for i in inputs if i[1] != inputs[0][1]]) > 1:
        print(-1)
        exit()
    else:
        print(max(0,inputs[0][1]))
else:
    out = [-1] * n
    for item in inputs:
        s = item[0]
        c = item[1]
        if out[s-1] != -1 and out[s-1] != c:
            print(-1)
            exit()
        elif s == 1 and c == 0:
            print(-1)
            exit()
        else:
            out[s-1] = c

out[0] = max(out[0],1)
res = 0
for i in range(len(out)):
    if out[i] != -1:
        res += out[i] * 10 ** (n-i-1)
print(res)
        

### FIXED CODE ###

n,m= map(int,input().split())
inputs = []
for _ in range(m):
    inputs.append(list(map(int,input().split())))

if m == 0:
    if n == 1:
        print(0)
    else:
        print(10**(n-1))
    exit()
elif n == 1:
    if len([i[1] for i in inputs if i[1] != inputs[0][1]]) > 0:
        print(-1)    
    else:
        print(max(0,inputs[0][1]))
    exit()
else:
    out = [-1] * n
    for item in inputs:
        s = item[0]
        c = item[1]
        if out[s-1] != -1 and out[s-1] != c:
            print(-1)
            exit()
        elif s == 1 and c == 0:
            print(-1)
            exit()
        else:
            out[s-1] = c

out[0] = max(out[0],1)
res = 0
for i in range(len(out)):
    if out[i] != -1:
        res += out[i] * 10 ** (n-i-1)
print(res)
import math
import numpy as np

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

# a = np.array(a)
# ans = []
# while a.min() != 9999999:
#     min_index = a.argmin()
#     ans.append(min_index+1)
#     a[min_index] = 9999999

# print(' '.join([str(_) for _ in ans]))

l = []
for i in range(n):
    l.append([i+1, a[i]])

sl = sorted(l, key=lambda x: x[1])
sl0 = [r[0] for r in sl]
print(' '.join([str(_) for _ in sl0]))


### FIXED CODE ###

import math
import numpy as np

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

# a = np.array(a)
# ans = []
# while a.min() != 9999999:
#     min_index = a.argmin()
#     ans.append(min_index+1)
#     a[min_index] = 9999999

# print(' '.join([str(_) for _ in ans]))

l = []
for i in range(n):
    l.append([i+1, a[i]])

sl = sorted(l, key=lambda x: x[1])
sl0 = [r[0] for r in sl]
print(' '.join([str(_) for _ in sl0]))
from fractions import Fraction
import math

n = int(input())


ab = []
ba = []

a0 = 0
b0 = 0
ab0 = 0

for i in range(n):
    a, b = map(int, input().split())
    if a != 0 and b != 0:
        ab.append(Fraction(a, b))
        ba.append(Fraction(-b, a))
    elif a == 0 and b == 0:
        ab0 += 1
    elif a == 0 and b != 0:
        a0 += 1
    elif a != 0 and b == 0:
        b0 += 1


d_ab = dict()
d_ba = dict()

d_done = dict()

for i in range(len(ab)):
    cur = ab[i]

    if cur in d_ab:
        d_ab[cur] += 1
    else:
        d_ab[cur] = 1

    cur = ba[i]

    if cur in d_ba:
        d_ba[cur] += 1
    else:
        d_ba[cur] = 1

mod = 1000000007

ans = 1

for k, v in d_ab.items():
    x = v
    if k in d_ba:
        if k in d_done:
            continue
        else:
            y = d_ba[k]
            kake = 0
            kake += ((2**x) % mod + (2**y) % mod - 1)
            ans *= kake
            ans %= mod
            d_done[Fraction(-k.denominator, k.numerator)] = 1
    else:
        kake = (2**x) % mod
        ans *= kake
        ans %= mod

ans *= ((2**ab0) % mod)
ans %= mod
ans *= ((2**a0) % mod+(2**b0) % mod-1)
ans %= mod

print(ans-1)


### FIXED CODE ###

from collections import deque

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

maze = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    maze[a-1].append(b-1)
    maze[b-1].append(a-1)

seen = [0 for i in range(n)]

mile = [-1 for i in range(n)]

q = deque()

q.append(0)
seen[0] = 1

while len(q) != 0:
    cur = q.popleft()

    for nx in maze[cur]:
        if not seen[nx] == 1:
            mile[nx] = cur+1
            seen[nx] = 1
            q.append(nx)

print('Yes')
for i in range(n-1):
    print(mile[i+1])
N, Y = map(int, input().split())
yukichi = -1
ichiyo = -1
hideyo = -1
for a in range(N+1):
    for b in range(N+1-a):
        c = N - a - b
        total = 10000*a + 5000*b + 1000*c
        if total == Y and c >= 0:
            yukichi = a
            ichiyo = b
            hideyo = c

print(f'{yukichi} {ichiyo} {hideyo}')

### FIXED CODE ###

N, Y = map(int, input().split())
for a in range(N+1):
    for b in range(N+1-a):
        c = N - a - b
        total = 10000*a + 5000*b + 1000*c
        if total == Y:
            print(a, b, c)
            exit()
print('-1 -1 -1')
import sys
readline=sys.stdin.readline

N=int(readline())
A=list(map(int,readline().split()))
B=[0]*N
sumB=0
for i in range(N):
  B[i]=A[i]-(i+1)
  
B=sorted(B)
candi=[0]*3
candi[0]=B[N//2-1]
candi[1]=B[N//2]
candi[2]=B[N//2+1]

ans=10**10
for c in candi:
  res=0
  for i in range(N):
    res+=abs(B[i]-c)
  if res<ans:
    ans=res
print(ans)


### FIXED CODE ###

import sys
readline=sys.stdin.readline

N=int(readline())
A=list(map(int,readline().split()))
B=[0]*N
sumB=0
for i in range(N):
  B[i]=A[i]-(i+1)
  
B=sorted(B)
mid=0
if len(B)&1:
  mid=B[N//2]
else:
  mid=(B[N//2-1]+B[N//2])//2
  
ans=0
for i in range(N):
  ans+=abs(B[i]-mid)

print(ans)
import math
 
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

n = int(input())
print(lcm(2,n))

### FIXED CODE ###

import fractions

n = int(input())
print(n * 2 // fractions.gcd(2, n))
rate=input()
result=""
if rate<1200:
  result="ABC"
elif rate<2800:
  result="ARC"
else:
  result="AGC"
print(result)

### FIXED CODE ###

rate=int(input())
result=""
if rate<1200:
  result="ABC"
elif rate<2800:
  result="ARC"
else:
  result="AGC"
print(result)
input_N_L = input()
N, L = map( int, input_N_L.split() )

str_set = set()
for i in range( L ):
  str_set.add( input() )

sorted_str = ""
for s in sorted( str_set ):
  sorted_str += s
print( sorted_str )

### FIXED CODE ###

n, l = map( int, input().split( ' ' ) )
strs = sorted( [ input() for i in range(n) ] )
print( ''.join( strs ) )
a = input()
b = int('a')
c = b**3
print c

### FIXED CODE ###

int = int(input())

print(int**3)