Harryxun/stf_run huggingface dataset:
import sys
INF = 10 ** 11
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
from heapq import heapify,heappush,heappop   

def main():
    n = int(input())
    a = list(map(int,input().split()))
    m = []
    p = []
    z = 0
    for num in a:
        if num < 0:
            m.append(num)
        elif num > 0:
            p.append(num)
        else:
            z += 1
    
    ans = []
    if len(p) * len(m) > 0:
        num1 = p[-1]
        p.pop()
        num2 = m[-1]
        m.pop()
        for i in range(len(m)):
            ans.append((num1,m[i]))
            num1 -= m[i]
        for i in range(len(p)):
            ans.append((num2,p[i]))
            num2 -= p[i]
        ans.append((num1,num2))
        num1 -= num2
    
    elif len(p) == 0:
        m.sort()
        num1 = m[-1]
        m.pop()
        for i in range(len(m)):
            ans.append((num1,m[i]))
            num1 -= m[i]
    
    elif len(m) == 0:
        p.sort()
        num1 = p[0]
        for i in range(1,len(p) - 1):
            ans.append((num1,p[i]))
            num1 -= p[i]
        ans.append((p[-1],num1))
        num1 = p[-1] - num1
    
    for i in range(z):
        ans.append((num1,0))
    print(num1)
    for i in range(n - 1):
        print(*ans[i])

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
INF = 10 ** 11
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
from heapq import heapify,heappush,heappop   

def main():
    n = int(input())
    a = list(map(int,input().split()))
    m = []
    p = []
    z = 0
    for num in a:
        if num < 0:
            m.append(num)
        elif num > 0:
            p.append(num)
        else:
            z += 1
    
    ans = []
    
    if z == n:
        print(0)
        for i in range(n - 1):
            print(0,0)
        return

    if len(p) == 0:
        if z:
            num1 = 0
            z -= 1
        else:
            m.sort()
            num1 = m[-1]
            m.pop()
        for i in range(len(m)):
            ans.append((num1,m[i]))
            num1 -= m[i]
    
    elif len(m) == 0:
        if z:
            num1 = 0
            z -= 1
            idx = 0
        else:
            p.sort()
            num1 = p[0]
            idx = 1
        for i in range(idx,len(p) - 1):
            ans.append((num1,p[i]))
            num1 -= p[i]
        ans.append((p[-1],num1))
        num1 = p[-1] - num1
    
    elif len(p) * len(m) > 0:
        num1 = p[-1]
        p.pop()
        num2 = m[-1]
        m.pop()
        for i in range(len(m)):
            ans.append((num1,m[i]))
            num1 -= m[i]
        for i in range(len(p)):
            ans.append((num2,p[i]))
            num2 -= p[i]
        ans.append((num1,num2))
        num1 -= num2
    
    for i in range(z):
        ans.append((num1,0))
    print(num1)
    for i in range(n - 1):
        print(*ans[i])

if __name__=='__main__':
    main()
n=int(input())
T=[int(input()) for _ in range(n)]
T.sort(reverse=True)

def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(y, x%y)

ans=int(T[0]/gcd(T[0], T[1]))*T[1]
for i in range(2, n):
    ans=int(T[i]/gcd(ans,T[i]))*ans

print(ans)

### FIXED CODE ###

import numpy as np
n=int(input())
T=np.array([int(input()) for _ in range(n)], dtype=np.int64)

def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(y, x%y)

ans=1
for t in T:
    ans*=t//gcd(t, ans)

print(ans)
n, a, b = map(int, input().split())
mod = 10 **9 +7
fac = [1] * 200000
inv = [1] * 200000
for i in range(1,len(fac)):
    fac[i] = fac[i-1] * i % mod
    inv[i] = pow(fac[i], mod-2, mod)

facna = 1
facnb = 1
for i in range(n-a+1,n+1):
    facna = facna * i %mod
for i in range(n-b+1,n+1):
    facnb = facnb * i %mod
ret = pow(2,n,mod) - 1 - facna * inv[a] - facnb * inv[b]
ret = ret%mod
print(ret)


### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10 **9 +7
fac = [1] * 200001
inv = [1] * 200001
for i in range(1,len(fac)):
    fac[i] = fac[i-1] * i % mod
    inv[i] = pow(fac[i], mod-2, mod)

facna = 1
facnb = 1
for i in range(n-a+1,n+1):
    facna = facna * i %mod
for i in range(n-b+1,n+1):
    facnb = facnb * i %mod
ret = pow(2,n,mod) - 1 - facna * inv[a] - facnb * inv[b]
ret = ret%mod
print(ret)
home = [[[0 for r in range(10)] for f in range(3)] for b in range(4)]
n = int(raw_input())
for i in range(n):
    b, f, r, v = map(int, raw_input().split())
    home[b-1][f-1][r-1] += v

for i in range(4):
    for j in range(3):
        print "",
        print " ".join(map(str, home[i][j]))
        if j == 2 and i != 3
            print "#" * 20


### FIXED CODE ###

n = int(input())
house = [[[0 for i in range(10)] for j in range(3)] for k in range(4)]
for i in range(n):
    b, f, r, v = map(int, input().split())
    house[b-1][f-1][r-1]+=v
    
for i in range(4):
    for j in range(3):
        for k in range(10):
            print(" "+str(house[i][j][k]), end="")
        print()
    if i != 3:
        print("#"*20)
import sys
readline = sys.stdin.readline
write = sys.stdout.write
flush = sys.stdout.flush

# クエリ: "? x1 x2" を出力
def query(x1):
    write("? %d\n" % (x1))
    flush()
    # ジャッジから返される値を取得
    return readline()

n = int(input())
l = 0
r = n-1
mid = r // 2
re = [None] * n
re[0] = query(0)
if re[0] == "Vacant":
  exit()
re[mid] = query(mid)
while re[mid] != "Vacant":
  if re[l] == re[mid]:
    if (mid - l) % 2:
      r = mid
    else:
      l = mid
  else:
    if (mid - l) % 2:
      l = mid
    else:
      r = mid
  mid = (l + r) // 2
  re[mid] = query(mid)
exit()

### FIXED CODE ###

import sys

n = int(input())
l = 0
r = n-1
mid = r // 2
re = [None] * n
print(0, flush=True)
re[0] = input()
if re[0] == "Vacant":
  sys.exit()
print(n-1, flush=True)
re[n-1] = input()
if re[n-1] == "Vacant":
  sys.exit()
print(mid, flush=True)
re[mid] = input()
while re[mid] != "Vacant":
  if re[l] == re[mid]:
    if (mid - l) % 2:
      r = mid
    else:
      l = mid
  else:
    if (mid - l) % 2:
      l = mid
    else:
      r = mid
  mid = (l + r) // 2
  print(mid, flush=True)
  re[mid] = input()
else:
  sys.exit()
import math
n, x = map(int, input().split())
cities = list(map(int, input().split()))
cities.append(x)
cities.sort()
 
def get_res(cities):
    if len(cities) == 2:
        return cities[1] - cities[0]
    elif len(cities) < 100:
        gcds = []
        for i in range(len(cities) - 2):
            c1 = cities[i]
            c2 = cities[i + 1]
            c3 = cities[i + 2]
            gcds.append(math.gcd(c2 - c1, c3 - c2))
        return min(gcds)
    else:
        return 100


print(get_res(cities))

### FIXED CODE ###

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

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

def get_res(cities):
    if len(cities) == 2:
        return cities[1] - cities[0]
    else:
        gcds = []
        for i in range(len(cities) - 2):
            c1 = cities[i]
            c2 = cities[i + 1]
            c3 = cities[i + 2]
            gcds.append(gcd(c2 - c1, c3 - c2))
        return min(gcds)

print(get_res(cities))
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,a,b = map(int,ipt().split())
    if a*b < n or a+b-1 > n:
        print(-1)
        exit()
    ans = [str(b-i)+" " for i in range(b)]
    si = n-a+2
    ue = n+1
    i = 0
    while True:
        if si <= b:
            break
        ans[i] += " ".join(map(str,range(si,ue)))
        ue = si
        si -= a-1
        i += 1
    if i < b:
        ans[i] += " ".join(map(str,range(b+1,ue)))
    print(" ".join(ans))
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,a,b = map(int,ipt().split())
    if a*b < n or a+b-1 > n:
        print(-1)
        exit()
    ans = [str(b-i) for i in range(b)]
    si = n-a+2
    ue = n+1
    i = 0
    while True:
        if si <= b or a == 1:
            break
        ans[i] += " "+" ".join(map(str,range(si,ue)))
        ue = si
        si -= a-1
        i += 1
    if i < b and b+1 < ue:
        ans[i] += " "+" ".join(map(str,range(b+1,ue)))
    print(" ".join(ans))
    return

if __name__ == '__main__':
    main()
A,B = map(int, input().split())
if a>= 13:
    print(B)
elif a>=6:
    print(B//2)
else:
    print(0)

### FIXED CODE ###

A,B = map(int, input().split())
if A>= 13:
    print(B)
elif A>=6:
    print(B//2)
else:
    print(0)
S=str(input())
ListNum=[]
ListNUM=[]
for i in range(0,len(S),1):
  if i<len(S)-2:
    Num=100*int(S[i])+10*int(S[i+1])+int(S[i+2])
    NUm=Num-753
    NUM=NUm**2
    ListNum.append(Num)
    ListNUm.append(NUm)
    ListNUM.append(NUM)
posi=ListNUM.index(min(ListNUM))
print(int(NUm[posi]))


### FIXED CODE ###

S=str(input())
ListNum=[]
ListNUm=[]
ListNUM=[]
for i in range(0,len(S),1):
  if i<len(S)-2:
    Num=100*int(S[i])+10*int(S[i+1])+int(S[i+2])
    NUm=Num-753
    NUM=NUm**2
    ListNum.append(Num)
    ListNUm.append(NUm)
    ListNUM.append(NUM)
posi=ListNUM.index(min(ListNUM))

if ListNUm[posi]<0:
  ListNUm[posi]=ListNUm[posi]*(-1)
print(ListNUm[posi])
from sys import stdin

while True:
    a, op, b = stdin.readline().rstrip().split()
    else if op == "+":
        print(int(a)+int(b))
    else if op == "-":
        print(int(a)-int(b))
    else if op == "*":
        print(int(a)*int(b))
    else if op == "/":
        print(int(a)//int(b))
    else: # op == "?"
        break



### FIXED CODE ###

from sys import stdin

while True:
    a, op, b = stdin.readline().rstrip().split()
    if op == "+":
        print(int(a)+int(b))
    elif op == "-":
        print(int(a)-int(b))
    elif op == "*":
        print(int(a)*int(b))
    elif op == "/":
        print(int(a)//int(b))
    else: # op == "?"
        break
n, x = map(int, input().split())
layers = [1]
pats = [1]
cnt = 1
p_cnt = 1
for _ in range(n):
  cnt = cnt * 2 + 3
  p_cnt = p_cnt * 2 + 1
  layers.append(cnt)
  pats.append(p_cnt)
def solve(lev, rest):
  if rest == 0:
    return 0
  if rest - 1 <= (layers[lev] - 3) // 2:
    return solve(lev - 1, rest - 1)
  elif rest - 1 == (layers[lev] - 3) // 2:
    return pats[lev - 1] + 1
  else:
    return pats[lev - 1] + 1 + solve(lev - 1, rest - 1 - layers[lev - 1] - 1)

print(solve(n, x))

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n, x = map(int, input().split())
layers = [1]
pats = [1]
cnt = 1
p_cnt = 1
for _ in range(n):
  cnt = cnt * 2 + 3
  p_cnt = p_cnt * 2 + 1
  layers.append(cnt)
  pats.append(p_cnt)
def solve(lev, rest):
  if rest == 0:
    return 0
  if lev == 0:
    return 1
  if rest - 1 <= layers[lev - 1]:
    return solve(lev - 1, rest - 1)
  elif rest - 1 == layers[lev - 1]:
    return pats[lev - 1] + 1
  else:
    return pats[lev - 1] + 1 + solve(lev - 1, rest - 1 - layers[lev - 1] - 1)

print(solve(n, x))
import sys
input = sys.stdin.readline

# D - .. (Double Dots)
from collections import deque

def set_route(start, goal):
	global routes
	
	routes[goal].append(start)


def search(que):
	global routes
	global guides

	if len(que) > 0:
		goal = que.popleft()

		for start in routes[goal]:
			if guides[start] == 0:
				guides[start] = goal
				que.append(start)
		
		search(que)
	else:
		return 


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

# 空の辞書(routes)を作成
for i in range(1, n + 1):
	routes[i] = []

# すべての出入り口の情報を取得("routes"に保存)
for i in range(m):
	a, b = map(int, input().split())
	set_route(a, b)
	set_route(b, a)

# 道しるべ(最後に出力)を保存するためのリスト
guides = [0] * (n + 1)

que = deque()
que.append(1)
search(que)

ans = guides[2:]

if 0 in ans:
	print('No')
else:
	print('Yes')
	
	for a in ans:
		print(a)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# D - .. (Double Dots)
from collections import deque
sys.setrecursionlimit(pow(10, 6))

def set_route(start, goal):
	global routes
	
	routes[goal].append(start)


def search(que):
	global routes
	global guides

	if len(que) > 0:
		goal = que.popleft()

		for start in routes[goal]:
			if guides[start] == 0:
				guides[start] = goal
				que.append(start)
		
		search(que)
	else:
		return 


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

# 空の辞書(routes)を作成
for i in range(1, n + 1):
	routes[i] = []

# すべての出入り口の情報を取得("routes"に保存)
for i in range(m):
	a, b = map(int, input().split())
	set_route(a, b)
	set_route(b, a)

# 道しるべ(最後に出力)を保存するためのリスト
guides = [0] * (n + 1)

que = deque()
que.append(1)
search(que)

ans = guides[2:]

if 0 in ans:
	print('No')
else:
	print('Yes')
	
	for a in ans:
		print(a)
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
for _ in range(4):
	N,K,X,Y=int(input())
	
print(N*X-(max((N-K),0)*(X-Y))


### FIXED CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N=int(input())
K=int(input())
X=int(input())
Y=int(input())

	
print(N*X-(max((N-K),0)*(X-Y)))
n = int(input())
a = list(map(int, input().split()))
if a.count('Y') == 0:
  print('Three')
else:
  print('Four')

### FIXED CODE ###

n = int(input())
a = list(map(str, input().split()))
if a.count('Y') == 0:
  print('Three')
else:
  print('Four')
line=input().split()
x=int(line[0])
y=int(line[1])
r=x%y
while(r>0):
    x=y
    y=r
    r=x%y
return y

print(y)



### FIXED CODE ###

line=input().split()
x=int(line[0])
y=int(line[1])
def gcd(x,y):
    r=x%y
    while(r>0):
        x=y
        y=r
        r=x%y
    return y
    
print (gcd(x,y))
n,k=map(int,input().split())
a=list(map(int,input().split()))

left=0
right=10**9
while left<right:
  cnt=0
  mid=(left+right)//2
  for i in range(n):
    cnt+=a[i]//mid
  if cnt<=k:
    right=mid
  else:
    left=mid+1
print(left)

### FIXED CODE ###

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

left=1
right=10**9
while left<right:
  cnt=0
  mid=(left+right)//2
  for i in range(n):
    cnt+=math.ceil(a[i]/mid)-1
  if cnt<=k:
    right=mid
  else:
    left=mid+1
print(left)
H, W = map(int, input().split(" "))

result = True
masu = [[0 for i in range(H+2)] for j in range(W+2)]
for h in range(1, H+1):
    s = "0"+input()+"0"
    masu[h] = list(s)

print(masu)    

for h in range(H+2):
    for w in range(W+2):
        if masu[h][w] == "#":
            if (masu[h][w] == masu[h+1][w]) or (masu[h][w] == masu[h][w+1]) or (masu[h][w] == masu[h-1][w]) or (masu[h][w] == masu[h][w-1]):
                pass
            else:
                result = False

if result:
    print("Yes")
else:
    print("No")

### FIXED CODE ###


H, W = map(int, input().split(" "))

# result = True
masu = [['.' for i in range(W+2)] for j in range(H+2)]
for h in range(H):
    s = "."+input()+"."
    masu[h+1] = s

# print(masu)

for h in range(1,H+1):
    for w in range(1,W+1):
        if masu[h][w] == "#":
            if "#" == masu[h+1][w] or "#" == masu[h][w+1] or "#" == masu[h-1][w] or "#" == masu[h][w-1]:
                pass
            else:
                # result = False
                print("No")
                exit()

print("Yes")
a,b,k = map(int,input().split())

for i in range(k):
  if a >= 1:
    a -= 1
  elif b >= 1:
    b -= 1
  else:
    pass

print(a,b)

### FIXED CODE ###

s,t = input().split()

print(t+s)
n,m=input().split()
n=int(n)
m=int(m)
a = input().split()
for i in range(m):
  a[i]=int(a[i])
  
if n>=m :
  sum=0
else:
  b=[]
  sum=0
  for i in range(m):
    b+=[a[i+1]-a[i]]
  b.sort().reverse()
  for i in range(N-1):
    sum+=b[i]
print(sum)
  

### FIXED CODE ###

n,m=input().split()
n=int(n)
m=int(m)
a = input().split()
for i in range(m):
  a[i]=int(a[i])
a.sort()
  
if n>=m :
  sum=0
else:
  b=[]
  sum=a[m-1]-a[0]
  for i in range(m-1):
    b+=[a[i+1]-a[i]]
  b.sort()
  b.reverse()
  for i in range(n-1):
    if b[i]>0:
      sum-=b[i]
    else:
      sum+=b[i]
print(sum)
s=input()
l=[]
alf=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o",
"p","q","r","s","t","u","v","w","x","y","z"]
for x in alf:
    if str(x) in s:
        pass
    else:
        l.append(x)
print(min(l))


### FIXED CODE ###

s=input()
l=[]
alf=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o",
"p","q","r","s","t","u","v","w","x","y","z"]
for x in alf:
    if str(x) in s:
        pass
    else:
        l.append(x)
if l==[]:
    print("None")
else:
    print(min(l))
N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

color = [0 for _ in range(N)]

def f(v,c):
    color[v] = c
    for i in range(len(graph[v])):
        if color[ graph[v][i] ] ==c:
            return False
        elif color[graph[v][i]] ==0 and not f(graph[v][i],-c):
            return False
    return True 

k = 1
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            k = -1

if k == 1: # 二部グラフ
    ans = color.count(1)*color.count(-1) - M
else:
    ans = M*(M-1)/2 - M

print(int(ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)


def f(u,c):
    color[u] = c
    for v in graph[u]:
        if color[v] == 0: # まだ塗られていない場合
            if not f(v,-c):
                return False
        else:
            if color[v] == c: # 隣接している頂点が同色の場合 二部グラフではない
                return False
    return True 

flag = True
color = [0 for _ in range(N)]
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            flag = False
            break

if flag: # 二部グラフ
    ans = color.count(1)*color.count(-1) - M
else:
    ans = N*(N-1)//2 - M

print(int(ans))
ans=""
for i in input():
  if x=="B":
    t=t[:-1]
print(ans)

### FIXED CODE ###

t=""
for i in input():
  if i=="B":
    if len(t)!=0:
      t=t[:-1]
  else:t+=i
print(t)
# AtCorder-Candy Distribution Again

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

a = 0
i = 0
list.sort()

if x < list[0]:
    print(0)

elif x >= list[0]:

    while x >= list[i] and x > 0:
        x -= list[i]
        a += 1
        if i < n-1 and x < list[i+1]:
            break
        if i == n-1:
            if x > list[i]:
                a = n-1
            else:
                a = n
            break
        i += 1

    print(a)


### FIXED CODE ###

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

a = 0
i = 0

list.sort()

if list[0] > x:
    print(0)

elif x > sum(list):
    print(n-1)

else:
    while x > 0 and x >= list[i]:
        x -= list[i]
        i += 1
        a += 1
        if i == n:
            break

    print(a)
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
q = int(input())
 
f = [a,b,c,d,e]

 
g=f[4]-f[3]
h=f[4]-f[2]
i=f[4]-f[1]
j=f[4]-f[0]
k=f[3]-f[2]
l=f[3]-f[1]
m=f[3]-f[0]
n=f[2]-f[1]
o=f[2]-f[0]
p=f[1]-f[0]

 
if g<q and h<q and i<q and j<q and k<q and l<q and m<q and m<q and n<q and o<q p<q:
  print("Yay!")
 
else:
  print(":(")

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
q = int(input())
 
f=e-d
g=e-c
h=e-b
i=e-a
j=d-c
k=d-b
l=d-a
m=c-b
n=c-a
o=b-a

 
 
if f<=q and g<=q and h<=q and i<=q and j<=q and k<=q and l<=q and m<=q and n<=q and o<=q:
  print("Yay!")
 
else:
  print(":(")
import itertools

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

count = 0
for V in itertools.permutations(range(1, N)):
    if V[0] in E[0] and all(V[i] in E[V[i-1]] for i in range(1, N-1)):
        count += 1
print(count)        


### FIXED CODE ###

import itertools

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

count = 0
for V in itertools.permutations(range(1, N)):
    if V[0] in E[0] and all(V[i] in E[V[i-1]] for i in range(1, N-1)):
        count += 1
print(count)
from sys import stdin
N, M = [int(x) for x in stdin.readline().rstrip().split()]
data = [stdin.readline().rstrip().split() for _ in range(M)]

island = list(range(N))
counts = [1] * N
total = int((N * (N - 1)) / 2)
result = []

for c in reversed(data):
    ref0 = int(c[0]) - 1
    while island[ref0] != ref0:
        ref0 = island[ref0]
    ref1 = int(c[1]) - 1
    while island[ref1] != ref1:
        ref1 = island[ref1]

    if ref0 == ref1:
        root = min(ref0, ref1)
        pair = max(ref0, ref1)
        island[int(c[0]) - 1] = root
        island[int(c[1]) - 1] = root
        island[pair] = root
        result.append(0);
    else:
        root = min(ref0, ref1)
        island[int(c[0]) - 1] = root
        island[int(c[1]) - 1] = root
        island[pair] = root
        result.append(counts[ref0] * counts[ref1]);
        counts[root] = counts[ref0] + counts[ref1]

res = [total]
for r in result:
    res.append((res[-1] - r))

print('\n'.join(reversed([str(x) for x in res][:-1])))


### FIXED CODE ###

from sys import stdin
N, M = [int(x) for x in stdin.readline().rstrip().split()]
data = [stdin.readline().rstrip().split() for _ in range(M)]

island = list(range(N))
counts = [1] * N
total = int((N * (N - 1)) / 2)
result = []

for c in reversed(data):
    ref0 = int(c[0]) - 1
    while island[ref0] != ref0:
        ref0 = island[ref0]
    ref1 = int(c[1]) - 1
    while island[ref1] != ref1:
        ref1 = island[ref1]

    if ref0 == ref1:
        result.append(0);
    else:
        island[max(ref0,ref1)] = min(ref0, ref1)
        result.append(counts[ref0] * counts[ref1]);
        counts[min(ref0,ref1)] = counts[ref0] + counts[ref1]

res = [total]
for r in result:
    res.append((res[-1] - r))

print('\n'.join(reversed([str(x) for x in res][:-1])))
N, K = map(int, input().split())
h_list = list(map(int, input().split()))

dp_list = [0]
for n in range(1, N):
  tmp_h = h_list[n]
  if n < K:
    lst = [abs(tmp_h - h_list[i]) + dp_list[i] for i in range(n)]
    else:
      lst = [abs(tmp_h - h_list[n-k]) + dp_list[n-k] for k in range(1, K + 1)]
      dp_list.append(min(lst))
      print(dp_list[-1])

### FIXED CODE ###

N = int(input())
h_list = list(map(int, input().split()))
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
import numpy as np
dp_list = [np.inf] * N
dp_list[0] = 0
dp_list[1] = abs(h_list[1] - h_list[0])
for i in range(2, N):
    dp_list[i] = chmin(dp_list[i], dp_list[i-1] + abs(h_list[i-1] - h_list[i]))
    dp_list[i] = chmin(dp_list[i], dp_list[i-2] + abs(h_list[i-2] - h_list[i]))
print(dp_list[-1])
n = input()
st1 = raw_input()
st2 = raw_input()
m = 1
mod = 1000000007
pat = 0 # or 1,2
bl = False
for i in range(n):
  if pat == 2 and bl:
    bl = False
    continue
  if st1[i] == st2[i] and pat = 0:
    m = m*3/mod
	pat = 1
  elif st1[i] == st2[i] and pat = 1:
    m = m*2/mod
    pat = 1
  elif st1[i] == st2[i] and pat = 2:
    m = m*2/mod
    pat = 1
  elif st1[i] != st2[i] and pat = 0:
    m = m*6/mod
    pat = 2
    bl = True
  elif st1[i] != st2[i] and pat = 1:
    m = m*2/mod
    pat = 2
    bl = True
  elif st1[i] != st2[i] and pat = 2:
    m = m*3/mod
    pat = 2
    bl = True
print m

### FIXED CODE ###

n = input()
st1 = raw_input()
st2 = raw_input()
m = 1
mod = 1000000007
pat = 0 # or 1,2
bl = False
for i in range(n):
  #print m
  if pat == 2 and bl:
    bl = False
    continue
  if st1[i] == st2[i] and pat == 0:
    m = m*3%mod
    pat = 1
  elif st1[i] == st2[i] and pat == 1:
    m = m*2%mod
    pat = 1
  elif st1[i] == st2[i] and pat == 2:
    pat = 1
  elif st1[i] != st2[i] and pat == 0:
    m = m*6%mod
    pat = 2
    bl = True
  elif st1[i] != st2[i] and pat == 1:
    m = m*2%mod
    pat = 2
    bl = True
  elif st1[i] != st2[i] and pat == 2:
    m = m*3%mod
    pat = 2
    bl = True
print m