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

def main():
    s_list = list(input())
    s_list.reverse()

    ans_list = [1]*10 + [0]*3 if s_list[0] == "?" else initial(int(s_list[0]))

    for i, s in enumerate(s_list):
        if i == 0:
            continue
        if s == "?":
            tmp_list = [0]*13
            for j in range(10):
                r = j * (10**i) % 13
                tmp_list = add(tmp_list, shift(r, ans_list))
            ans_list = tmp_list
        else:
            r = int(s)*(10**i) % 13
            ans_list = shift(r, ans_list)

    print(ans_list[5] % 1000000007)


def shift(r, ans_list):
    l = len(ans_list)
    return [ans_list[(i + l - r) % l] for i in range(l)]


def add(list1, list2):
    return list(map(sum, zip(list1, list2)))


def initial(n):
    return [(1 if i == n else 0) for i in range(13)]


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np


def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_l = amari_list(n)
    amari_m = amari_matrix(n, amari_l)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            ans_list = np.dot(ans_list, amari_m[i % len(amari_m)]) % mod
        else:
            t = int(s) * amari_l[i % len(amari_l)] % n
            ans_list = np.roll(ans_list, t)

    print(int(ans_list[r] % mod))


def initial(s, n):
    if s == "?":
        return np.array([1 if i < 10 else 0 for i in range(n)], dtype='int64')
    else:
        return np.array([1 if i == int(s) else 0 for i in range(n)], dtype='int64')


def shift(n, r):
    return np.array([[1 if (i - j + r) % n == 0 else 0 for j in range(n)] for i in range(n)])


def amari_list(n):
    ret = []
    for i in range(n + 1):
        r = 10**i % n
        if r in ret:
            return ret
        else:
            ret.append(r)


def amari_matrix(n, amari_list):
    ret = np.zeros((len(amari_list), n, n))
    for i, j in enumerate(amari_list):
        tmp = np.zeros((n, n))
        for k in range(10):
            tmp += shift(n, j * k % n)
        ret[i] = tmp
    return ret


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

from fractions import gcd
from functools import reduce
# from collections import deque
# from math import factorial
# import collections
import math
import sys
sys.setrecursionlimit(2000000)
# import itertools
# import statistics
# import numpy as np
# x = int(input())
a, b, n = list(map(int, input().split()))
# a, b = list(map(int, input().split()))
# sy, sx = map(int, input().split())
# gy, gx = map(int, input().split())

ans = a*n//b - a*(n//b)
count = 0
same = 0
# print(ans)
for i in range(n, int(pow(n, 0.75))-1, -1):
    if ans < a*i//b - a*(i//b):
        ans = a*i//b - a*(i//b)
        if count == 1:
            print(ans)
            exit()
    elif a*i//b - a*(i//b) == 0:
        count += 1
print(ans)

### FIXED CODE ###

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

x = min(b-1, n)
ans = a*x//b - a*(x//b)

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

n , m = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(m)]

d = [0]*n
for i in range(m):
  for j in range(lr[i][0]-1, lr[i][1]):
    d[j] += 1
    
print(d.count(m))

### FIXED CODE ###

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

a=0
b=n
for i in range(m):
  l, r = map(int, input().split())
  a = max(a, l)
  b = min(b, r)
if b-a+1 >= 0:
  print(b-a+1)
else:
  print(0)
### BUGGY CODE ###

# D - Div Game
from collections import deque

def pf(N):
    ans = deque([])
    p = 2
    while N>1:
        if N%p==0:
            k = 0
            while N%p==0:
                N //= p
                k += 1
            ans.append(k)
        p += 1+(p>2)
    return ans

def func(a):
    tmp = 0
    while True:
        a -= tmp+1
        if a<0:
            return tmp
        else:
            tmp += 1

N = int(input())
ans = 0
l = pf(N)
while len(l)>0:
    ans += func(l.popleft())
print(ans)

### FIXED CODE ###

# D - Div Game
from collections import deque

def pf(N):
    ans = deque([])
    p = 2
    while N>1:
        if N%p==0:
            k = 0
            while N%p==0:
                N //= p
                k += 1
            ans.append(k)
        p += 1+(p>2)
        if p**2>N:
            p = N
    return ans

def func(a):
    tmp = 0
    while True:
        a -= tmp+1
        if a<0:
            return tmp
        else:
            tmp += 1

N = int(input())
ans = 0
l = pf(N)
while len(l)>0:
    ans += func(l.popleft())
print(ans)
### BUGGY CODE ###

import os, sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")
 
sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10**18
MOD = 10**9 + 7

def n(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))
def bulk_li(): return list(map(lambda s: list(map(int, s.split())), sys.stdin.readlines()))

N = n()
abc = bulk_li()  # [[a_i, b_i, c_i]...]

# print(abc)

T = [
    [1, 2],
    [0, 2],
    [0, 1]
]

def solve(abc):
    dp = np.zeros((N, 3), dtype='int32')  # [[Ai, Bi, Ci]...]

    for j in range(3):
        dp[0][j] = abc[0][j]
    if N == 1:
        return dp

    for i in range(N-1):
        dp[i+1][0] = abc[i+1][0] + np.max(dp[i][[1,2]])
        dp[i+1][1] = abc[i+1][1] + np.max(dp[i][[0,2]])
        dp[i+1][2] = abc[i+1][2] + np.max(dp[i][[0,1]])

    # print(dp)
    return dp

print(max(solve(abc)[N-1]))


"""
ちゃんと解いたVer
"""


### FIXED CODE ###

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

if n > 1:
    for _ in range(n-1):
        a_, b_, c_ = list(map(int, input().split()))
        a_ += max(b, c)
        b_ += max(a, c)
        c_ += max(a, b)
        a, b, c = a_, b_, c_

print(max(a, b, c))
"""
ちゃんと解いたVer
"""
### BUGGY CODE ###

n = int(input())
paisen = [0] * n
person = list(map(int,input().split()))
for i in range(n) :
    paisen[i] = person.count(i+1)

for i in range(n) :
    print(paisen[i])

### FIXED CODE ###

n = int(input())
paisen = [0] * n
person = list(map(int,input().split()))
for i in range(n-1) :
    paisen[person[i]-1] += 1
for j in range(n) :
    print(paisen[j])
### BUGGY CODE ###

import queue
import copy

def replace(s, n, c):
    if n < 0 or n >= len(s):
        return s
    return s[:n]+c[0]+s[n+1:]

h, w = map(int, input().split())
l = [input() for _ in range(h)]

def dist(m, x1, y1, x2, y2):
    q = queue.Queue()
    q.put((x1, y1, 0))
    checked=[[False for _ in range(w)] for __ in range(h)]
    while not q.empty():
        x, y, count = q.get()
        if (x, y) == (x2, y2):
            return count
        if x > 0 and m[y][x-1] == "." and checked[y][x-1] == False:
            checked[y][x-1] = True
            q.put((x-1, y, count+1))
        if y > 0 and m[y-1][x] == "." and checked[y-1][x] == False:
            checked[y-1][x] = True
            q.put((x, y-1, count+1))
        if x < w-1 and m[y][x+1] == "." and checked[y][x+1] == False:
            checked[y][x+1] = True
            q.put((x+1, y, count+1))
        if y < h-1 and m[y+1][x] == "." and checked[y+1][x] == False:
            checked[y+1][x] = True
            q.put((x, y+1, count+1))

ans = 0
for i in range(h):
    for j in range(w):
        for _i in range(h):
            for _j in range(w):
                if l[i][j] == "." and l[_i][_j] == ".":
                    ans = max(ans, dist(l, j, i, _j, _i))
print(ans)

### FIXED CODE ###

import queue
import copy

h, w = map(int, input().split())
l = [input() for _ in range(h)]

def dist(m, x1, y1):
    q = queue.Queue()
    q.put((x1, y1, 0))
    checked=[[False for _ in range(w)] for __ in range(h)]
    checked[y1][x1] = True
    while not q.empty():
        x, y, count = q.get()
        if x > 0 and m[y][x-1] == "." and checked[y][x-1] == False:
            checked[y][x-1] = True
            q.put((x-1, y, count+1))
        if y > 0 and m[y-1][x] == "." and checked[y-1][x] == False:
            checked[y-1][x] = True
            q.put((x, y-1, count+1))
        if x < w-1 and m[y][x+1] == "." and checked[y][x+1] == False:
            checked[y][x+1] = True
            q.put((x+1, y, count+1))
        if y < h-1 and m[y+1][x] == "." and checked[y+1][x] == False:
            checked[y+1][x] = True
            q.put((x, y+1, count+1))
    return count

ans = 0
for i in range(h):
    for j in range(w):
        if l[i][j] == ".":
            ans = max(ans, dist(l, j, i))
print(ans)
### BUGGY CODE ###

import math
n, m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
sorted_a = sorted(a, reverse=True)
for i in range(m):
    sorted_a[0] = math.floor(sorted_a[0]/2)
    new_a = sorted(sorted_a, reverse=True)
    sorted_a = new_a
print(sum(sorted_a))

### FIXED CODE ###

import heapq
n, m = (int(i) for i in input().split())
a = [int(i) * (-1) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    tmp_min = ((a[0] * (-1)) //2) * (-1)
    heapq.heappushpop(a,tmp_min)
print(abs(sum(a)))
### BUGGY CODE ###

x=int(input())
s=set()
l=[i for i in range(1,x)]

for i in reversed(l):
  if x%i == 0:
    a=i+x//i-2
    s.add(a)
    if min(s)-a <0:
      break
print(min(s))


### FIXED CODE ###

import math
x=int(input())
s=set()
y=int(math.sqrt(x))
for i in range(y,0,-1):
  if x%i == 0:
    a=i+x//i-2
    s.add(a)
    if min(s)-a <0:
      break
print(min(s))
### BUGGY CODE ###

s = input()
q = int(input())
quest = [0]*q
state = 0
for i in range(q):
    que = input().split()
# for que in quest:
    if (que[0] == '1'):
        # 反転は計算量が多いので一度だけする。
        state = 1 - state
        continue
    else:
        if (state == 0 and que[1] == '1'):
            s = que[2] + s
        elif(state == 0 and que[1] == '2'):
            s = s + que[2]
        elif (state == 1 and que[1] == '1'):
            s = s + que[2]
        else:
            s = que[2] + s

if (state == 1):
    s = s[::-1]
print(s)


### FIXED CODE ###

s = input()
q = int(input())
quest = [0]*q
state = 0
former, latter = '', ''
for i in range(q):
    que = input().split()
# for que in quest:
    if (que[0] == '1'):
        # 反転は計算量が多いので一度だけする。
        state = 1 - state
        continue
    else:
        if (state == 0 and que[1] == '1'):
            former = que[2] + former
        elif(state == 0 and que[1] == '2'):
            latter = latter + que[2]
        elif (state == 1 and que[1] == '1'):
            latter = latter + que[2]
        else:
            former = que[2] + former

if (state == 1):
    print(latter[::-1] + s[::-1] + former[::-1])
else:
    print(former + s + latter)
### BUGGY CODE ###

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

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

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr) 
ans=1
for val in arr:
 ans*=val 
 if ans>10**18:
   print(-1)
   break
else:
 print(ans)
### BUGGY CODE ###

N=int(input())
C=[]
A=[]
B=[]
ans=0
for i in range(N):
  a=str(input())
  C.append(a)
for i in C:
  ab=[j for j in i]
  ab.sort()
  aaa="".join(ab)
  #print(aaa)
  if aaa in A:
    i=A.index(aaa)
    ans+=B[i]
    B[i]+=1
  else:
    A.append(aaa)
    B.append(1)
print(ans)

### FIXED CODE ###

N=int(input())
C=[]
dic={}
ans=0
for i in range(N):
  a=str(input())
  C.append(a)
for i in C:
  ab=[j for j in i]
  ab.sort()
  aaa="".join(ab)
  #print(aaa)
  if aaa in dic:
    ans+=dic[aaa]
    dic[aaa]+=1
  else:
    dic[aaa]=1
print(ans)
#print(dic)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        if mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
sys.stdout.flush()import sys
input=sys.stdin.readline
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        if mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
        sys.stdout.flush()
print(0)
start=input()
sys.stdout.flush()
if start=='Vacant':exit()
bin(start)

print(0)
start=input()
sys.stdout.flush()
if start=='Vacant':exit()
bin(start)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        elif mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
sys.stdout.flush()
start=input()
if start=='Vacant':exit()
bin(start)
### BUGGY CODE ###

from collections import deque

h,w,K = map(int,input().split())

maze = [[x for x in input()] for _ in range(h)]

sx = 0
sy = 0

for i in range(h):
    for j in range(w):
        if maze[i][j] == 'S':
            sx = j
            sy = i

d = [[float('inf')]*w for _ in range(h)]
d[sy][sx] = 0

q = deque([[sy,sx]])
c = 0

visited = [[False]*w for _ in range(h)]
visited[sy][sx] = True

while q:
    y,x = q.popleft()
    for j,k in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny,nx = y+j,x+k
        if maze[ny][nx] == '.' and not visited[ny][nx]:
            d[ny][nx] = d[y][x] + 1
            if ny in {0,h-1} or nx in {0,w-1}:
                if d[ny][nx] <= K:
                    print(1)
                    exit()
                else:
                    continue
            else:
                visited[ny][nx] = True
                if d[ny][nx] == K:
                    continue
                else:
                    q.append([ny,nx])
    

def BFS(sy,sx):
    visited = [[-1]*w for _ in range(h)]
    q = deque([[sy,sx]])
    visited[sy][sx] = 0
    while q:
        y,x = q.popleft()
        if y == 0 or y == h-1 or x == 0 or x == w-1:
            return visited[y][x]
        for l,k in [[1,0],[-1,0],[0,1],[0,-1]]:
            new_y,new_x = y+l,x+k
            if visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                q.append([new_y,new_x])

ans = float('inf')

for i in range(h):
    for j in range(w):
        if d[i][j] <= K:
            ans = min(ans,BFS(i,j))

print((ans-1) // K +2)

### FIXED CODE ###

from collections import deque

h,w,K = map(int,input().split())

maze = [[x for x in input()] for _ in range(h)]

sx = 0
sy = 0

for i in range(h):
    for j in range(w):
        if maze[i][j] == 'S':
            sx = j
            sy = i

d = [[float('inf')]*w for _ in range(h)]
d[sy][sx] = 0

q = deque([[sy,sx]])
c = 0

visited = [[False]*w for _ in range(h)]
visited[sy][sx] = True

while q:
    y,x = q.popleft()
    for j,k in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny,nx = y+j,x+k
        if maze[ny][nx] == '.' and not visited[ny][nx]:
            d[ny][nx] = d[y][x] + 1
            if ny in {0,h-1} or nx in {0,w-1}:
                if d[ny][nx] <= K:
                    print(1)
                    exit()
                else:
                    continue
            else:
                visited[ny][nx] = True
                if d[ny][nx] == K:
                    continue
                else:
                    q.append([ny,nx])
    

def BFS(sy,sx):
    visited = [[-1]*w for _ in range(h)]
    q = deque([[sy,sx]])
    visited[sy][sx] = 0
    while q:
        y,x = q.popleft()
        if y == 0 or y == h-1 or x == 0 or x == w-1:
            return visited[y][x]
        for l,k in [[1,0],[-1,0],[0,1],[0,-1]]:
            new_y,new_x = y+l,x+k
            if visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                q.append([new_y,new_x])

ans = float('inf')

for i in range(h):
    for j in range(w):
        if d[i][j] <= K:
            ans = min(ans,min(i,h-1-i,j,w-1-j))

print((ans-1) // K +2)
### BUGGY CODE ###

n=int(input())
a=list(map(str,input().split()))
l=[a[0]]
if n%2==0:
    for i in range(1,n):
        if i%2==1:
            l=[a[i]]+l
        else:
            l=l+[a[i]]
    print(" ".join(map(str,l)))
else:
    for i in range(1,n):
        if i%2==0:
            l=[a[i]]+l
        else:
            l=l+[a[i]]
    print(" ".join(map(str,l)))

### FIXED CODE ###

from collections import deque
n=int(input())
a=list(map(str,input().split()))
l=deque()
if n%2==0:
    for i in range(n):
        if i%2==1:
            l.appendleft(a[i])
        else:
            l.append(a[i])
    print(" ".join(map(str,l)))
else:
    for i in range(n):
        if i%2==0:
            l.appendleft(a[i])
        else:
            l.append(a[i])
    print(" ".join(map(str,l)))
### BUGGY CODE ###

def main():
  n = int(input())
  S = input()
  q = int(input())
  K = list(map(int, input().split()))
  for k in K:
    d = 0
    m = 0
    dm = 0
    dmc = 0
    for s in S[:k-1]:
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
    for s,e in zip(S[k-1:],S):
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
      if e == "D":
        d -= 1
        dm -= m
      elif e == "M":
        m -= 1
    print(dmc)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  n = int(input())
  S = input()[:-1]
  q = int(input())
  K = map(int, input().split())
  for k in K:
    d = 0
    m = 0
    dm = 0
    dmc = 0
    for s in S[:k-1]:
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
    for s,e in zip(S[k-1:],S):
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
      if e == "D":
        d -= 1
        dm -= m
      elif e == "M":
        m -= 1
    print(dmc)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

n=int(input())
A=[list(map(int,input().split()))for _ in[0]*n]
p=[0]*2**n
p[0]=1
for I in range(2**n-1):
 a=A[bin(I).count('1')]
 for j in range(n):
  if(I>>j)%2<a[j]:p[I|1<<j]+=p[I]
print(p[-1]%(10**9+7))

### FIXED CODE ###

n=int(input());
A=[int(input().replace(' ',''),2)for _ in[0]*n]
dp=[0]*2**n
dp[0]=1
for I in range(2**n-1):
    a=A[bin(I).count('1')]&~I
    for j in range(n):
        if a&1<<j:dp[I|1<<j]=(dp[I|1<<j]+dp[I])%(10**9+7)
print(dp[-1])
### BUGGY CODE ###

def main(n,ab,px):
  g=[[]for _ in range(n+1)]
  for a,b in ab:
    g[a].append(b)
    g[b].append(a)
  # 各頂点を根とした部分木に含まれる頂点を列挙
  d={i:[i] for i in range(1,n+1)}
  def dfs():
    todo=[[1]]
    while len(todo)>0:
      c=todo.pop()
      l=g[c[-1]]
      for li in set(l)-set(c):
        for ci in c:
          d[ci].append(li)
        ct=c.copy()
        ct.append(li)
        todo.append(ct)
  dfs()
  ans=[0]*n
  for p,x in px:
    for di in d[p]:
      ans[di-1]+=x
  print(' '.join(list(map(str,ans))))

if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n,q=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(n-1)]
  px=[list(map(int,input().split())) for _ in range(q)]
  main(n,ab,px)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
def main():
    n,q=map(int,input().split())
    graph=[[] for _ in range(n+1)]
    ab=[list(map(int,input().split())) for _ in range(n-1)]
    for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
    px=[list(map(int,input().split())) for _ in range(q)]
    seen=[0]*(n+1)
    ans=[0]*(n+1)
    for p,x in px:
        ans[p]+=x
    def dfs(i):
        seen[i]=1
        for li in graph[i]:
            if seen[li]==0:
                ans[li]+=ans[i]
                dfs(li)
    dfs(1)
    print(' '.join(map(str,ans[1:])))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
import math
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(n, cnt):
  aoki_visited[n] = True
  aoki[n] = cnt
  for x in edge[n]:
    if aoki_visited[x] == False:
      tami(x, cnt+1)

def tami2(n, cnt):
  choku_visited[n] = True
  if cnt <= aoki[n]:
    choku[n] = cnt
    for x in edge[n]:
      if choku_visited[x] == False:
        tami2(x, cnt+1)

N, u, v = IL()
ab = [IL() for _ in range(N-1)]

aoki = [0]*(N+1)
aoki_visited = [False]*(N+1)
choku = [0]*(N+1)
choku_visited = [False]*(N+1)

edge = [[] for _ in range(N+1)]
for a,b in ab:
  edge[a].append(b)
  edge[b].append(a)

ans = 0
tami(v, 0)
tami2(u, 0)
#print(aoki)
#print(choku)

for i in range(N+1):
  if choku[i] == 0 and i != u:
    continue
  if aoki[i] > choku[i]:
    ans = max(ans, aoki[i] - 1)

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    s.S = {}
    s.P = {}
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            if i not in s.S:
              s.S[i] = [j]
            else:
              s.S[i].append(j)
            s.P[j] = i

      s.D += 1
      F = Ft
  def getDeep(s, x):
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n):
    if n == 0:
      return x
    return s.getParent(s.P[x], n - 1)
    

N, u, v = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N - 1)]

T = Tree(N)
for a, b in AB:
  T.setC(a - 1, b - 1)

T.makeRank(v - 1)
t = (T.R[u - 1] // 2) - 1
f = T.R[u - 1] % 2
k = T.getDeep(T.getParent(u - 1, t))
print(t + k + f)
### BUGGY CODE ###

nm=list(map(int,input().split()))
n=nm[0]
m=nm[1]

inp=[]
if m==0:
    inp=[n+1]
    dis=[n+1]
else:
    for inpset in range(m):
        inp.append(int(input()))
    

    dis=[max(inp[0],1)]
    p=0
    for i in inp[:-1]:
        dis.append(inp[p+1]-inp[p]-1)
        p+=1
    dis.append(max(n-inp[-1],1))
    #print (dis)

import math

def kaijo(x):
    ans=(math(100000)%1000000007)
    return ans

def combinations_count(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))%1000000007

def counting(x):
    if x==1:
        return 1
    else:
        
        res=0
        for a in range(x-1):
            if x-1-a>=a:
                res+=combinations_count(x-1-a,a)
                # print(x-1-a,a)
            else:
                break
        res=res%1000000007
        return res

if 0 in dis:
    print(0)
else:
    ans=1
    dis.sort()
    for d in dis:
        ans*=counting(d)
        ans=ans%1000000007
    print(ans)


### FIXED CODE ###

nm=list(map(int,input().split()))
n=nm[0]
m=nm[1]

inp=[]
if m==0:
    inp=[n+1]
    dis=[n+1]
else:
    for inpset in range(m):
        inp.append(int(input()))
    

    dis=[max(inp[0],1)]
    p=0
    for i in inp[:-1]:
        dis.append(inp[p+1]-inp[p]-1)
        p+=1
    dis.append(max(n-inp[-1],1))
    #print (dis)

def fib(x):
    a=0
    b=1
    for step in range(x):
        c=a+b
        a=b
        b=c
    return a


def counting(x):
    if x==1:
        return 1
    else:
        
        res=0
        for a in range(x-1):
            if x-1-a>=a:
                res+=combinations_count(x-1-a,a)
                # print(x-1-a,a)
            else:
                break
        res=res%1000000007
        return res

if 0 in dis:
    print(0)
else:
    ans=1
    dis.sort()
    for d in dis:
        ans*=fib(d)%1000000007
        ans=ans%1000000007
    print(ans)