Harryxun/stf_run huggingface dataset:
A1 = list(map(int,input().split()))
A2 = list(map(int,input().split()))
A3 = list(map(int,input().split()))
A = A1 + A2 + A3
N = int(input())
for i in range(N):
  B = int(input())
  if B == A[i]:
    A[i] == 'AC'
if A[0] == A[1] == A[2] == 'AC' or A[3] == A[4] == A[5] == 'AC' or A[6] == A[7] == A[8] == 'AC':
  print('Yes')
elif A[0] == A[3] == A[6] == 'AC' or A[1] == A[4] == A[7] == 'AC' or A[2] == A[5] == A[8] == 'AC':
  print('Yes')
elif A[0] == A[4] == A[8] == 'AC' or A[2] == A[4] == A[6] == 'AC':
  print('Yes')
else:
  print('No')

### FIXED CODE ###

A1 = list(input().split())
A2 = list(input().split())
A3 = list(input().split())
A = [A1,A2,A3]
N = int(input())
for i in range(N):
  C = input()
  for j in range(3):
    if C == A[0][j]:
      A[0][j] = 'AC'
    if C == A[1][j]:
      A[1][j] = 'AC'
    if C == A[2][j]:
      A[2][j] = 'AC'
for l in range(3):
    if A[l][0] == A[l][1] == A[l][2] == 'AC':
      print('Yes')
      exit()
    if A[0][l] == A[1][l] == A[2][l] == 'AC':
      print('Yes')
      exit()
if A[0][0] == A[1][1] == A[2][2] == 'AC':
  print('Yes')
  exit()
if A[0][2] == A[1][1] == A[2][0] == 'AC':
  print('Yes')
  exit()
print('No')
n=int(input())
lists=[list(input().split()) for x in range(n)]
for x in range(n):
  a,b=input().split()
  lists.append([a,int(b),x+1])
lists.sort(key=lambda t:t[1],reverse=True)
lists.sort(key=lambda t:t[0])
for x in range(n):
  print(lists[x][2])

### FIXED CODE ###

n=int(input())
lists=[]
for x in range(n):
  a,b=input().split()
  lists.append([a,int(b),x+1])
lists.sort(key=lambda t:t[1],reverse=True)
lists.sort(key=lambda t:t[0])
for x in range(n):
  print(lists[x][2])
s = input()
for i in range(26):
    if chr(97+i) not in s: 
        print(chr(97+i)) 
        break
    if i == 25:
        print("None")
l.sort(reverse=True)
print(sum(l[:k]))
s = input()
for i in range(1,len(s)-1):
	if (len(s) - i) % 2 == 1: pass
	elif s[:(len(s) - i)//2] == s[(len(s) - i)//2:-i]:
		print(len(s) - i)
		#print(s[:-i])
		break

### FIXED CODE ###

#!/usr/bin/env python3
s = input()
for i in range(1,len(s)-1):
	if (len(s) - i) % 2 == 1: pass
	elif s[:(len(s) - i)//2] == s[(len(s) - i)//2:-i]:
		print(len(s) - i)
		#print(s[:-i])
		break
from functools import reduce
import fractions

N,X = map(int,input().split())
xn = list(map(int,input().split()))
xn.append(X)
xn.sort()
distance = [xn[i]-xn[i-1] for i in range(1,N)]
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
print(gcd_list(distance))

### FIXED CODE ###

from functools import reduce
import fractions

N,X = map(int,input().split())
xn = list(map(int,input().split()))

distance = [abs(X-xn[i]) for i in range(N)]
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
print(gcd_list(distance))
N,K=map(int,input().split())
light=list(map(int,input().split()))
copy=[0]*N
for k in range(K):
  imo=[0]*(N+1)
  x=0
  for i in range(N):
    kido=light[i]
    imo[max(0,i-kido)]+=1
    imo[min(N-1,i+kido)+1]-=1
  for j in range(N+1):
    x+=imo[j]
    copy[j]=x
  if light==copy:
    break
  else:
    light=copy
print(*light)

### FIXED CODE ###

N,K=map(int,input().split())
light=list(map(int,input().split()))
for k in range(K):
  imo=[0]*(N+1)
  for i in range(N):
    l=max(0,i-light[i])
    r=min(N-1,i+light[i])+1
    imo[l]+=1
    imo[r]-=1
  for i in range(1,N):
    imo[i]+=imo[i-1]
  if light==imo:
    break
  else:
    light=imo[:]
print(*light[:-1])
n = int(input())
l = list(map(int,input().split()))
l.sort()

ans = 0
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if l[k]<l[i]+l[j]:
        if l[i]!=l[j] and l[j]!=l[k]:
            ans +=1
            
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if l[i] != l[j] != l[k]:
                if l[i] + l[j] > l[k]:
                    ans += 1
print(ans)
#
# abc090 b
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """11009 11332"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """31415 92653"""
        output = """612"""
        self.assertIO(input, output)


def resolve():
    A, B = map(int, input().split())
    ans = 0
    for i in range(A, B+1):
        s = str(i)
        for j in range((3):
            if s[j] != s[-1-j]:
                break
        else:
            ans += 1
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

#
# abc090 b
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """11009 11332"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """31415 92653"""
        output = """612"""
        self.assertIO(input, output)


def resolve():
    A, B = map(int, input().split())
    ans = 0
    for i in range(A, B+1):
        s = str(i)
        for j in range((len(s)+1)//2):
            if s[j] != s[-1-j]:
                break
        else:
            ans += 1
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()
S = int(input())
h = S // 3600
m = S % 3600 // 60
s = S // 60
print(h,m,s sep=':')

### FIXED CODE ###

import sys
S = int(sys.stdin.readline())
h = int(S / 60 / 60)
m = int(S % 3600 / 60)
s = S % 60
print("%d:%d:%d" % (h, m, s))
x,n=map(int,input().split())

if n==0:
    print(x)
else:
    p=list(map(int,input().split()))

    num=[1]*101
    count=1

    for i in p:
        num[i]=0   
    if num[x]==1:
        print(x)
    while True:
        if x-count>-1:
            if num[x-count]==1:
                print(x-count)
                break
        if x+count<102:
            if num[x+count]==1:
                print(x+count)
                break    
        count+=1

### FIXED CODE ###

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

if n==0:
    print(x)
else:
    p=list(map(int,input().split()))

    num=[1]*102
    count=1

    for i in p:
        num[i]=0   
    if num[x]==1:
        print(x)
    else:
        while True:
            if x-count>-1:
                if num[x-count]==1:
                    print(x-count)
                    break
            if x+count<103:
                if num[x+count]==1:
                    print(x+count)
                    break    
            count+=1
print(input().count('1))

### FIXED CODE ###

print(input().count("1"))
s=input()
a_1=s.count("1")
b_1=s.cpunt("0")
if a_1<=b_1:
  print(2*a_1)
else:
  print(2*b_1)

### FIXED CODE ###

s=input()
a_1=s.count("1")
b_1=s.count("0")
if a_1<=b_1:
  print(2*a_1)
else:
  print(2*b_1)
n,d=map(int,input().split())
x=[]
for _ in range(d):
  x+=[list(map(int,input().split()))]
ans=0
for i in range(d):
  for j in range(i+1,d):
    l=0
    for k in range(n):
      l+=(x[i][k]-x[j][k])**2
    if l==l**0.5**2:
      ans+=1
print(ans)

### FIXED CODE ###

n,d=map(int,input().split())
x=[]
for _ in range(n):
  x+=[list(map(int,input().split()))]
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    dist=0
    for k in range(d):
      dist+=(x[i][k]-x[j][k])**2
    dist=dist**0.5
    if dist.is_integer():
      ans+=1
print(ans)
import heapq
import math
class Graph:
    def __init__(self,v,w_e,w_v = None):
        super().__init__()
        self.v = v

        self.w_v = w_v
        self.w_e = [{} for _ in [0]*self.v]


        self.neighbor = [[] for _ in [0]*self.v]
        for a_i,b_i,w_i in w_e:
            self.w_e[a_i][b_i] = w_i#weight of edge
            self.neighbor[a_i].append(b_i)

    def dijkstra(self,v_n):
        d = [math.inf]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

def main():
    h,w = tuple([int(t)for t in input().split()])

    c = [[int(t) for t in input().split()]for _ in [0]*10]

    a = [[int(t) for t in input().split()]for _ in [0]*h]

    counter = [0]*10
    for a_i in a:
        for a_ij in a_i:
            if a_ij != -1:
                counter[a_ij]+=1

    w_e = []
    for i in range(10):
        for j in range(10):
            w_e.append((i,j,c[i][j]))
    
    g = Graph(10,w_e)

    routes = []
    for i in range(10):
        routes.append(g.dijkstra(i)[0])

    ans = 0
    for i in range(10):
        if i!=1:
            ans += routes[i][1]*counter[i]

    print(ans)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq
import math
class Graph:
    def __init__(self,v,w_e,w_v = None):
        super().__init__()
        self.v = v

        self.w_v = w_v
        self.w_e = [{} for _ in [0]*self.v]


        self.neighbor = [[] for _ in [0]*self.v]
        for a_i,b_i,w_i in w_e:
            self.w_e[a_i][b_i] = w_i#weight of edge
            self.neighbor[a_i].append(b_i)

    def dijkstra(self,v_n):
        d = [10**18]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

def main():
    h,w = tuple([int(t)for t in input().split()])

    c = [[int(t) for t in input().split()]for _ in [0]*10]

    a = [[int(t) for t in input().split()]for _ in [0]*h]

    counter = [0]*10
    for a_i in a:
        for a_ij in a_i:
            if a_ij != -1:
                counter[a_ij]+=1

    w_e = []
    for i in range(10):
        for j in range(10):
            w_e.append((i,j,c[i][j]))
    
    g = Graph(10,w_e)

    routes = []
    for i in range(10):
        routes.append(g.dijkstra(i)[0])

    ans = 0
    for i in range(10):
        if i!=1:
            ans += routes[i][1]*counter[i]

    print(ans)


if __name__ == "__main__":
    main()
N =input()
A = (map(int, input().split()))

for a in A:
    ans *= a
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
  

### FIXED CODE ###

n = int(input())
a = [i for i in map(int, input().split())]
 
if a.count(0) != 0:
  print(0)
else:
  result = 1
  for i in range(n):
    result *= a[i]
    if result > (10**18):
      print(-1)
      break
    else:
      continue
  else:
    print(result)
#editorial参照
import sys
from collections import deque
n,m = map(int, input().split( ))
G = [[] for _ in range(n)]

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

if m&1:
    print(-1)
    sys.exit()

Tr = [0]*n#k木に属しているか
Q = deque()
Q.append(0)
Tr[0] = 1
TrE = [[] for _ in range(n)]
P = [-1]*n#親
Leaf = []
while Q:
    v = Q.popleft()
    leaf_v = True
    for u in G[v]:
        if not Tr[u]:
            Tr[u] = 1
            P[u]=v
            TrE[v].append(u)
            Q.append(u)
            leaf_v = False
    if leaf_v:
        Leaf.append(v)

out = [0]*n
D = set()             
for v in range(n):
    for u in G[v]:
        if (u,v) not in D and P[v]!=u and P[u]!=v:
            D.add((v,u))
            out[v]^=1
            

"""
幅優先探索で葉から辿ったところ、
すべての子を考慮する前にpのdegreeが決まってしまっている。
深さ優先探索に修正
"""
def dfs(x = 0, parent = -1):
    for y in TrE[x]:
        if y == parent:
            continue
        dfs(y,x)
        if out[y]:
            D.add((y,x))
            out[y] ^= 1
        else:
            D.add((x,y))
            out[x] ^= 1
 
dfs()

for u,v in D:
    print(u+1,v+1)

### FIXED CODE ###

#editorial参照

import sys
from collections import deque
sys.setrecursionlimit(200000)

n,m = map(int, input().split( ))
G = [[] for _ in range(n)]

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

if m&1:
    print(-1)
    sys.exit()

Tr = [0]*n#k木に属しているか
Q = deque()
Q.append(0)
Tr[0] = 1
TrE = [[] for _ in range(n)]
P = [-1]*n#親
Leaf = []
while Q:
    v = Q.popleft()
    leaf_v = True
    for u in G[v]:
        if not Tr[u]:
            Tr[u] = 1
            P[u]=v
            TrE[v].append(u)
            Q.append(u)
            leaf_v = False
    if leaf_v:
        Leaf.append(v)

out = [0]*n
D = set()             
for v in range(n):
    for u in G[v]:
        if (u,v) not in D and P[v]!=u and P[u]!=v:
            D.add((v,u))
            out[v]^=1
            

"""
幅優先探索で葉から辿ったところ、
すべての子を考慮する前にpのdegreeが決まってしまっている。
深さ優先探索に修正
"""
def dfs(x = 0, parent = -1):
    for y in TrE[x]:
        if y == parent:
            continue
        dfs(y,x)
        if out[y]:
            D.add((y,x))
            out[y] ^= 1
        else:
            D.add((x,y))
            out[x] ^= 1
 
dfs()

for u,v in D:
    print(u+1,v+1)
data = [int(i) for i in input)_.split()]

data.sort()
print("{0}{1}{2}".format(data[0],data[1],data[2]))

### FIXED CODE ###

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

data.sort()
print("{0} {1} {2}".format(data[0],data[1],data[2]))
N = input()
A = input()
B = input()

N = int(N)
A = int(A)
B = int(B)

count = 0
i = 0

while 1:
  count = count + A + B
  i += 1
  if count > N:
    break

cut = N - (A+B)*(i-1)
print(cut)

if cut > A:
  Blue_Ball_Num = A*i
else:
  Blue_Ball_Num = A*i + ((A+B)*i - N)
  
print(Blue_Ball_Num)

### FIXED CODE ###

a = input().split()

N = int(a[0])
A = int(a[1])
B = int(a[2])

i = int(N/(A+B))

cut = N - (A+B)*i

if N < A:
  Blue_Ball_Num = N
elif N < A+B:
  Blue_Ball_Num = A
elif cut > A:
  Blue_Ball_Num = A*(i+1)
else:
  Blue_Ball_Num = A*i + (N - (A+B)*i)
  
print(Blue_Ball_Num)
n,m =map(int, input().split())
a =[list(input().split()) for i in range(m)]
ends = [0]*n
was = [0]*n
for num, kekka in a:
    num=int(num)-1
    if kekka=='AC':
        ends[num]=1
    else:
        if ends[num]!=1:
            was[num]+=1
for i in range(n):
    if end[i]==0:
        was[i]=0
print(sum(ends), sum(was))

### FIXED CODE ###

n,m =map(int, input().split())
a =[list(input().split()) for i in range(m)]
ends = [0]*n
was = [0]*n
for num, kekka in a:
    num=int(num)-1
    if kekka=='AC':
        ends[num]=1
    else:
        if ends[num]!=1:
            was[num]+=1
for i in range(n):
    if ends[i]==0:
        was[i]=0
print(sum(ends), sum(was))
import sys
import math
import bisect

def main():
    a = ''.join(input().split())
    if a % 4 == 0:
        print('YES')
    else:
        print('NO')
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math
import bisect

def main():
    r, g, b = map(int, input().split())
    val = r * 100 + g * 10 + b
    if val % 4 == 0:
        print('YES')
    else:
        print('NO')

if __name__ == "__main__":
    main()
def collatx(i):
    cnt=0
    while i!=1:
        cnt+=1
        if i%2==0:
            i//=2
        else:
            i*=3
            i+=1
    return cnt

def main():
    n=int(input())
    acc=0
    for i in range(1,n+1):
        acc+=collatx(i)
        acc%=1000000007
    print(acc)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

l,r,d=map(int,input().split())
print(r//d-(l-1)//d)
N = int(input())
pritn((N+1)//2)

### FIXED CODE ###

N = int(input())
print((N+1)//2)
N, M = map(int, input().split())
cnt = [0 for i in range(n + 1)] 
check = []
ans = []

for i in range(m):
    p, y = map(int, input().split())
    check.append((y, p, i))

check.sort()

for y, p, i in check:
    cnt[p] += 1
    ans.append((i,str(p).zfill(6)+str(cnt[p]).zfill(6)))

ans.sort()

for aa, bb in ans:
    print(bb)

### FIXED CODE ###

N, M = map(int, input().split())
cnt = [0 for i in range(N + 1)] 
check = []
ans = []

for i in range(M):
    p, y = map(int, input().split())
    check.append((y, p, i))

check.sort()

for y, p, i in check:
    cnt[p] += 1
    ans.append((i,str(p).zfill(6)+str(cnt[p]).zfill(6)))

ans.sort()

for aa, bb in ans:
    print(bb)
import numpy as np
from numba import njit, int64
import sys

read = sys.stdin.buffer.read


@njit((int64, int64[:], int64[:], ), cache=True)
def pre_calc(n, pos, coef):
    ret = np.empty((1 << n, n), np.int64)
    ret[0] = np.abs(pos) * coef

    for i in range(n):
        bt = 1 << i
        ret[bt:2 * bt] = np.minimum(ret[:bt], np.abs(pos - pos[i]) * coef)

    return ret


@njit((int64[:], ), cache=True)
def solve(inp):
    INF = 10 ** 18

    n = inp[0]
    x = inp[1::3]
    y = inp[2::3]
    p = inp[3::3]

    ver = pre_calc(n, x, p)
    hor = pre_calc(n, y, p)

    states = np.zeros((2, pow(3, n)), np.int16)
    cnts = np.zeros(pow(3, n), np.int8)
    for i in range(pow(3, n)):
        pw2 = 1
        now = i
        for j in range(n):
            r = now % 3
            if r != 0:
                states[r - 1, i] += pw2
                cnts[i] += 1
            pw2 *= 2
            now //= 3

    vals = np.minimum(ver[states[0]], hor[states[1]]).sum(axis=1)
    ans = [INF] * (n + 1)
    for ev, ec in zip(vals, cnts):
        ans[ec] = min(ans[ec], ev)

    return ans


inp = np.array(read().split(), np.int64)
ans = solve(inp)
print(*ans, sep="\n")


### FIXED CODE ###

import numpy as np
from numba import njit, int64
import sys

read = sys.stdin.buffer.read


@njit((int64[:], ), cache=True)
def solve(inp):
    INF = 10 ** 18

    n = inp[0]
    x = inp[1::3]
    y = inp[2::3]
    p = inp[3::3]

    ver = np.empty((1 << n, n), np.int64)
    ver[0] = np.abs(x) * p

    for i in range(n):
        bt = 1 << i
        ver[bt:2 * bt] = np.minimum(ver[:bt], np.abs(x - x[i]) * p)

    hor = np.empty((1 << n, n), np.int64)
    hor[0] = np.abs(y) * p

    for i in range(n):
        bt = 1 << i
        hor[bt:2 * bt] = np.minimum(hor[:bt], np.abs(y - y[i]) * p)

    ans = [INF] * (n + 1)
    for i in range(pow(3, n)):
        vi = 0
        hi = 0
        cnt = 0
        pow2 = 1
        pow3 = i
        while pow3:
            pow3, r = divmod(pow3, 3)
            if r == 1:
                vi += pow2
                cnt += 1
            elif r == 2:
                hi += pow2
                cnt += 1

            pow2 *= 2

        score = np.minimum(ver[vi], hor[hi]).sum()
        ans[cnt] = min(ans[cnt], score)

    return ans


inp = np.array(read().split(), np.int64)
ans = solve(inp)
print(*ans, sep="\n")
from collections import deque
X,Y,Z,K=[int(i) for i in input().split()]
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(key=lambda x:-x)
B.sort(key=lambda y:-y)
C.sort(key=lambda z:-z)
pri=deque()
def dp(l):
  return A[l[0]]+B[l[1]]+C[l[2]]

def priq(a,b,c):
  if [a,b,c] not in pri:
    for i in range(len(pri)):      
      if dp(pri[i])>dp([a,b,c]):
        pri.insert(i,[a,b,c])
        return
    pri.append([a,b,c])
pri.append([0,0,0])
for i in range(K):
  x,y,z=pri.pop()
  print(dp([x,y,z]))
  if x<X-1:
    priq(x+1,y,z)
  if y<Y-1:
    priq(x,y+1,z)
  if z<Z-1:
    priq(x,y,z+1)



### FIXED CODE ###

import heapq
X,Y,Z,K=[int(i) for i in input().split()]
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(key=lambda x:-x)
B.sort(key=lambda y:-y)
C.sort(key=lambda z:-z)
pri=[]
def dp(x,y,z):
  return A[x]+B[y]+C[z]

def priq(a,b,c):
  d=-dp(a,b,c)
  if tuple([d,a,b,c]) not in pri:
    heapq.heappush(pri,(d,a,b,c))

heapq.heappush(pri,(-dp(0,0,0),0,0,0))

for i in range(K):
  d,x,y,z=heapq.heappop(pri)
  print(-d)
  if x<X-1:
    priq(x+1,y,z)
  if y<Y-1:
    priq(x,y+1,z)
  if z<Z-1:
    priq(x,y,z+1)
def dfs(i):
    if all(visited):
        global ans
        ans += 1
        return
    for j in range(N):
        if g[i][j] and not visited[j]:
            visited[j] = True
            dfs(j)
            visited[j] = False

N, M = map(int, input().split())
g = [[False] * M for _ in range(M)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a-1][b-1] = True
    g[b-1][a-1] = True

ans = 0
visited = [False] * N
visited[0] = True
dfs(0)
print(ans)

### FIXED CODE ###

def dfs(i):
    if all(visited):
        global ans
        ans += 1
        return
    for j in range(N):
        if g[i][j] and not visited[j]:
            visited[j] = True
            dfs(j)
            visited[j] = False

N, M = map(int, input().split())
g = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a-1][b-1] = True
    g[b-1][a-1] = True

ans = 0
visited = [False] * N
visited[0] = True
dfs(0)
print(ans)
# -*- coding: utf-8 -*-

A, B = map(int, input())

[print(A+B) if A+B < 10 else print('error')]

### FIXED CODE ###

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

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

[print(A+B) if A+B < 10 else print('error')]
import math 
def lcm(x,y):
    return x*y//math.gcd(x,y)
n,m = map(int,input().split())
a = list(map(int,input().split()))
gcds = a[0]
for i in a:
    gcds = lcm(gcds,i)
a = [i//2 for i in a]
a_0 = a[0]
for i in a:
    a_0 = lcm(a_0,i)
#print(a_0,gcds)
if a_0 < m:
    ans = math.ceil((m - a_0) // gcds)
elif a_0 == m:
    ans = 1
else:
    ans = 0
print(ans)

### FIXED CODE ###

k,x = map(int,input().split())
if k*500 >= x:
    print("Yes")
else:
    print("No")
n, a, b = map(int, input().split())
t = 'r' * a + 'b' * b
t=(t*n)[0:n]
print(t.count('r'))

### FIXED CODE ###

n, a, b = map(int, input().split())
t = a + b
count = t if t > 0 else 0
r = 0
if count == 0:
	r = 0
else:
	d = int(n/t)
	if d*t == n:
		r = d * a
	else:
		r = d * a
		e = n - d*t
		if e <= a:
			r = r + e
		else:
			r = r + a
print(r)
N,M,X,Y=map(int, input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
x.apped(X)
y.apped(Y)
print('War' if max(x)>=min(y) else 'No War')

### FIXED CODE ###

N,M,X,Y=map(int, input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
print("No War" if (max(x)<min(y) and X<Y and X<min(y) and Y>max(x)) else "War")
S = input()
for i in range(len(S)+1):
  if i == len(S):
    print('Yes')
    break
  if S[i] =='U' or S[i] =='D':
    pass
  else:
    if S[i] % 2 ==0:
      if S[i] == 'R':
        pass
      else:
        print('No')
        break
    else:
      if S[i]== 'L':
        pass
      else:
        print('No')
        break
        
      
    


### FIXED CODE ###

S = input()
for i in range(len(S)+1):
  if i == len(S):
    print('Yes')
    break
  if S[i] =='U' or S[i] =='D':
    pass
  else:
    if i % 2 ==0:
      if S[i] == 'R':
        pass
      else:
        print('No')
        break
    else:
      if S[i]== 'L':
        pass
      else:
        print('No')
        break