Harryxun/stf_run huggingface dataset:
import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    d, g = MI()
    data = np.array(sys.stdin.buffer.read().split(), np.int64)
    data = data.reshape(-1, 2)
    p = data[:, 0]
    c = data[:, 1]

    problems = np.zeros(2 ** d, np.int64)
    points = np.zeros(2 ** d, np.int64)
    for i in range(d):
        problems[1 << i : 1 << (i + 1)] = problems[: 1 << i] + p[i]
        points[1 << i : 1 << (i + 1)] = points[: 1 << i] + c[i] + 100 * (i + 1) * p[i]

    for i in range(2 ** d):
        while points[i] < g:
            for j in reversed(range(d)):
                if (i >> j) & 1:
                    continue
                for _ in range(p[j]):
                    if points[i] >= g:
                        break
                    points[i] += 100 * (j + 1)
                    problems[i] += 1

    print(problems.min())


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


inf = float("inf")


def main():
    d, g = MI()
    pc = [LI() for _ in range(d)]

    ans = inf
    for bit in range(2 << d):
        c = 0
        score = 0
        for i in range(d):
            if bit & (1 << i):
                c += pc[i][0]
                score += pc[i][0] * 100 * (i + 1) + pc[i][1]

        if score >= g:
            ans = min(ans, c)
        else:
            for i in reversed(range(d)):
                if bit & (1 << i):
                    continue
                res = math.ceil((g - score) / (100 * (i + 1)))
                if res < pc[i][0]:
                    ans = min(ans, c + res)
                break

    print(ans)


if __name__ == "__main__":
    main()
#bin/usr/env python3

n, a, b, c, d = map(int,input().split())
s = input()
s_li = []

for i in s:
    s_li.append(i)

last = c
reach = True

if last < d:
    last = d

if c < d:
    for i in range(a-1,last-1):
        if(s_li[i] == "#" and s_li[i+1] == "#"):
            reach = False
            break

elif d < c:
    for i in range(a-1,last-1):
        if(s_li[i] == "#" and s_li[i+1] == "#"):
            reach = False
            break
        reach = False

        if(s_li[i+2] == "." and s_li[i] == "." and s_li[i+1] == "."):
            reach = True
            break

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


### FIXED CODE ###

n,a,b,c,d = map(int,input().split())
sub = "#"+input()
s = list(sub)

con = True
for i in range(a,d+1):
    if s[i-1]=="#" and s[i]=="#":
        print("No")
        con = False
        break

if (con):
    if (c<b) or (c<d):
        print("Yes")
        con = False

if (con):
    for i in range(b-1,d):
        if s[i]=="." and s[i+1]=="." and s[i+2]==".":
            print("Yes")
            con = False
            break

if (con):
    print("No")
from math import gcd
a, b = [int(tem) for tem in input().split()]
print(str(gcd(a, b)))

### FIXED CODE ###

a, b = [int(tem) for tem in input().split()]

def mak(A, B) :
    while B != 0 :
        q, r = divmod(A, B)
        A = int((A - r) / q)
        B = r
    return A

if a > b : print(mak(a, b))
else     : print(mak(b, a))
S = input("先週のコンテスト名を入力")

if S == ABC:
  print(ARC)
  
else:
  print(ABC)

### FIXED CODE ###

S = input()

if S == "ABC":
  print("ARC")
  
else:
  print("ABC")
N = input()

cnt=0

for i in range(1,N+1):
    if len(str(i)) %2 != 0:
        cnt+=1
print(cnt)

### FIXED CODE ###

N = int(input())
 
cnt=0
 
for i in range(1,N+1):
    if len(str(i)) %2 != 0:
        cnt+=1
print(cnt)
import sys
input = sys.stdin.readline

#intの場合
N ,M = map(int,input().split())

intlist = list(map(int, input().split()))
newlist = sorted(intlist, reverse=True)[:M]

if newlist[M-1] > ( sum(intlist) / (4 * M) ):
  print ("Yes")
else:
  print ("No")
  

### FIXED CODE ###

import sys
input = sys.stdin.readline

#intの場合
X,Y,Z = map(int,input().split())

Xa = Y
Ya = X
Xa = Z
Za = Y

print ( Z, X ,Y)
s=input()
k=int(input())

count_1=0
while s!='':
  if s[0]=='1':
    count_1+=1
    s=s.lstrip('1')
if count_1>=k:
  print('1')
else:
  print(s[0])


### FIXED CODE ###

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

count_1=0
while s!='':
  if s[0]=='1':
    count_1+=1
    s=s[1:]
  else:
    break
if count_1>=k:
  print('1')
else:
  print(s[0])
A, B, K = map(int, input().split())
if B - A < 2 * K:
    # print(*range(A, B + 1))
    print(*list(range(A, B + 1)))
else:
    # print(*range(A, A + K), *range(B - K + 1, B + 1))
    print(*list(range(A, A + K)), *list(range(B - K + 1, B + 1)))


### FIXED CODE ###

A, B, K = map(int, input().split())
if B - A < 2 * K:
    # ans = [*range(A, B + 1)]
    ans = list(range(A, B + 1))
else:
    # ans = [*range(A, A + K), *range(B - K + 1, B + 1)]
    ans = list(range(A, A + K)) + list(range(B - K + 1, B + 1))
for v in ans:
    print(v)
while True:
    [a,b,c]=[x for x in input().split()]
    a,b=int(a),int(b)
    if a==0 and b==0:
        break
    elif op=="+":
        print(a+b)
    elif op=="-":
        print(a-b)
    elif op=="*"
        print(a*b)
    else:
        print(a//b)

### FIXED CODE ###

while True:
    [a,b,c]=[x for x in input().split()]
    [a,c]=[int(a),int(c)]
    op=b
    if op=="?":
        break
    elif op=="+":
        print(a+c)
    elif op=="-":
        print(a-c)
    elif op=="*":
        print(a*c)
    else:
        print(a//c)
s = input()
s =input()
ab = [chr(97+i) for i in range(26)]
res = 'None'
for i in ab:
    if i not in s:
        res = i
        break
print(res)

### FIXED CODE ###

s =input()
ab = [chr(97+i) for i in range(26)]
res = 'None'
for i in ab:
    if i not in s:
        res = i
        break
print(res)
import sys
N = int(input())
A = [int(input()) for _ in range(N)]
ans = 1
a = A.index(1)+1
#print(a)
for i in range(N*2):
    a = A[a-1]
    #print(a)
    if a == 2:
        print(ans)
        sys.exit()
    ans += 1
print(-1)

### FIXED CODE ###

import sys
N = int(input())
A ={}
for i in range(1,N+1):
    A[i] = int(input())
#print(A)
ans = 1
x = 1
for j in range(N):
    if A[x] == 2:
        print(ans)
        sys.exit()
    x = A[x]
    ans += 1
print(-1)
N,M = map(int,input().split())
a_list = []
b_list = []
c_list = []
for _ in range(M):
    a, b = map(int,input().split())
    c = list(map(int,input().split()))
    c = [cc-1 for cc in c]
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)


takara_keys = {}
for i in range(N):
    takara = []
    for idx, c in enumerate(c_list):
        if i in c:
            takara.append(idx)
    takara_keys[i] = takara

clear = [1 for _ in range(N)]
def dp(memos, cost):
    if memos == clear:
        return cost
    costs = [10**9]
    for takara, memo in enumerate(memos):
        if memo == 0:
            next_keys = takara_keys[takara]
            for key in next_keys[0]:
                tmp_memos = memos[:]
                for takara_idx in c_list[key]:
                    tmp_memos[takara_idx] = 1
                tmp_cost = cost + a_list[key]
                costs.append(dp(tmp_memos,tmp_cost))
    return min(costs)

length_0_flag = False
for v in takara_keys.values():
    if len(v)==0:
        length_0_flag = True

if length_0_flag:
    print(-1)
else:
    print(dp([0 for _ in range(N)],0))

### FIXED CODE ###

#解説放送見てからの書き直し
import sys
import os
INF = 10**12
ans = INF
N, M = map(int,input().split())
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
C = []
for i in range(M):
    a, b = map(int,input().split())
    A[i] = a  #鍵の金額
    B[i] = b  #開けられる宝箱の種類数
    tmp = list((map(int,input().split())))
    s = 0
    for j in range(b):
        t = tmp.pop(0)-1
        s |= 1 << t
    C.append(s)
    
dp = [INF]*(1<<N) #2^N
dp[0] = 0 #0 = 0b0000の時、スコアは0（まだ1つも鍵を購入してないので）

for s in range(1<<N): #1<<Nは2^N。つまりどの宝箱が開くかの全ての状態
    for j in range(M): # 全ての鍵について見ていく
        t = s | C[j] # 論理和。sには現在どの宝箱が開けられるかの状態、
                     # C[j]にはその新たな鍵が開ける宝箱。
                     # その論理和はこれまでの鍵と新たな鍵でどの宝箱が開けられるか
        cost = dp[s] + A[j] # その鍵を買った時のコスト
        dp[t] = min(dp[t],cost) #新たな宝箱の状態について、コストがより低くなるようなら保存する。
ans = dp[-1] #dp[-1]、つまり0b1111。宝箱が全て開けられる状態。
if ans == INF: #もし0b1111がINFのまま（最初から変わってない）ということはそこにたどり着けなかったということ。
               #つまり、全ての鍵を使っても宝箱を開けられなかった。
    ans = -1
print(ans)
from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
init_small = int(arr, 2) % (cnt - 1)

li = []
for i in range(n):
    if arr[i] == "0":
        li.append((init_big + (1 << (n - i - 1))) % (cnt + 1))
    else:
        li.append((init_small - (1 << (n - i - 1))) % (cnt - 1))


ans = []

for x in li:
    ans.append(rec(x) + 1)

if int(arr, 2) == 1:
    ans[-1] = 0

print(*ans, sep="\n")

### FIXED CODE ###

from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


ret = [rec(x) for x in range(2 * 10**5 + 1)]


n = int(input())
arr = input()

ALL_ARR = int(arr, 2)

cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)


li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(ret[x] + 1)

print(*ans, sep="\n")
n=input()
l=len(n)
k=int(input())
def f(n,k):
  l=len(n)
  if n[0]=="0":return f(n[1:],k)
  if l<k:return 0
  if k==1:
    ans=((l-1)*9)+int(n[0])
  if k==2:
    ans=((l-1)*(l-2)//2)*81+(int(n[0])-1)*((l-1)*9)
    ans+=f(n[1:],k-1)
  if k==3:
    ans=(int(n[0])-1)*((l-1)*(l-2)//2)*81+((l-1)*(l-2)*(l-3)//6)*9*9*9
    ans+=f(n[1:],k-1)
  return ans
print(f(n,k))

### FIXED CODE ###

n=input()
k=int(input())
dp=[[(k+1)*[0]for _ in range(2)]for _ in range(len(n))]
#dp[i][flag][j]...i文字目までみて0以外がj個あるパターン数
#flag...True(n[])
dp[0][0][0]=1
dp[0][1][1]=1
dp[0][0][1]=int(n[0])-1
for i in range(1,len(n)):
  for j in range(k+1):dp[i][1][j]=dp[i-1][1][j]
  if n[i]!="0":dp[i][1]=[0]+dp[i][1][:k]
  for j in range(k+1):dp[i][0][j]=dp[i-1][0][j]
  for j in range(k):
    dp[i][0][j+1]+=dp[i-1][0][j]*9
    if n[i]!="0":
      dp[i][0][j+1]+=dp[i-1][1][j]*(int(n[i])-1)
      dp[i][0][j+1]+=dp[i-1][1][j+1]
print(dp[-1][0][-1]+dp[-1][1][-1])
#for i in dp:print(*i)
def bin_search(arr,k):
    low, high = 0, n - 1
    while (low <= high):
        mid= low+(high-low)//2
        if arr[mid]==k:
            return mid
        if arr[mid]>k:
            high=mid-1
        else:
            low=mid+1

x,n= map(int,input().split(' '))
if n!=0:
    arr= list(map(int,input().split(' ')))
    arr.sort()
    idx= bin_search(arr,x)

    l,r=-1,-1
    for i in range(1,idx):
        left= arr[idx-i]
        if x-left>i:
            l=(arr[idx-i+1]-1)
            break
    if l==-1:
        l=arr[0]-1
    for i in range(1,n-idx):
        right= arr[idx+i]
        if right-x>i:
            r=(arr[idx+i-1]+1)
            break
    if r==-1:
        r=arr[n-1]+1
    if (x-l)<=(r-x):
        print(l)
    else:
        print(r)
else:
    print(x)

### FIXED CODE ###

x,n= map(int,input().split(' '))
if n!=0:
    arr= list(map(int,input().split(' ')))
    for j in range(x+1):
        for i in range(-1,2):
            if arr.count(x+i*j)==0:
                print(x+i*j)
                exit(0)
else:
    print(x)
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 10**9 + 7
k = int(input())
s = input()

def make_tables(n, mod = 10 ** 9 + 7):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

    for i in range(2, n + 1):
        fac.append((fac[-1] * i) % mod)
        inv.append((mod -inv[mod % i] * (mod // i)) % mod)
        finv.append((finv[-1] * inv[-1]) % mod)
    return fac, finv

def nCk(n, k, mod = 10 ** 9 + 7):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

##########################
fac, finv = make_tables(10**6)
ans = 1
for i in range(k + 1):
    temp = 1
    temp *= 26**i
    temp %= mod
    j = k - i
    if j == 0:
        ans += temp
        continue
    temp *= 25**j
    temp %= mod
    temp *= nCk(j - 1 + len(s), j - 1)
    ans += temp
    ans %= mod
print(ans)





### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 10**9 + 7
k = int(input())
s = input()
n = len(s)

def make_tables(n, mod = 10 ** 9 + 7):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

    for i in range(2, n + 1):
        fac.append((fac[-1] * i) % mod)
        inv.append((mod -inv[mod % i] * (mod // i)) % mod)
        finv.append((finv[-1] * inv[-1]) % mod)
    return fac, finv

def nCk(n, k, mod = 10 ** 9 + 7):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

##########################
fac, finv = make_tables(2*10**6 + 1)
ans = 0
for i in range(k + 1):
    temp = 1
    temp *= pow(26, i, mod)
    temp %= mod
    j = k - i
    if j == 0:
        ans += temp
        continue
    temp *= pow(25, j, mod)
    temp %= mod
    temp *= nCk(n + j - 1, n - 1)
    ans += temp
    ans %= mod
print(ans % mod)
import math
from functools import reduce
n,s=map(int,input().split())
x=list(map(int,input().split()))
#print(x)

for i in range(n):
    x[i]=abs(x[i]-s)

gcd=reduce(math.gcd,x)

print(gcd)

### FIXED CODE ###

import fractions
from functools import reduce
n,s=map(int,input().split())
x=list(map(int,input().split()))
#print(x)

for i in range(n):
    x[i]=abs(x[i]-s)

print(reduce(fractions.gcd,x))
n = int(input())
p = [int(i) for i in input().split()]
count = 0
for i in range(n):
    if p[i] != i + 1:
        count += 1
if count == 0:
    print('YES')

if count == 2:
    print('YES')

if count > 2:
    print('No')


### FIXED CODE ###

A, B = list(map(int, input().split()))
C = A + B
if C%2 == 0:
    answer = (A + B)/2
    print(int(answer))
else:
    answer = 'IMPOSSIBLE'
    print(answer)
a=input()
b=a/3
print(b**3)
exit(0)

### FIXED CODE ###

a = int(input())
b=a/3
print(b**3)
exit()
N, M, X = map(int, input().split())
C = [0] * N
A = []

for __ in range(N):
    nums = list(map(int, input().split()))
    C[__] = nums[0]
    A.append(nums[1:])
mincost = 10e9
ok = False
for i in range(1 << N):
    cost = 0
    skill = [0] * M

    for u in range(N):
        if i & (1<<u):
            cost += C[u]
            for si, s in enumerate(A[u]):
                skill[si] += s
    
    # check
    if all([s >= X for s in skill]):
        ok = True
        if mincost > cost:
            mincost = cost

print(mincost if ok else -1)
 dp


### FIXED CODE ###

N, M, X = map(int, input().split())
C = [0] * N
A = []

for __ in range(N):
    nums = list(map(int, input().split()))
    C[__] = nums[0]
    A.append(nums[1:])

mincost = 10e9
ok = False
for i in range(1 << N):
    cost = 0
    skill = [0] * M

    for u in range(N):
        if i & (1<<u):
            cost += C[u]
            for si, s in enumerate(A[u]):
                skill[si] += s
    
    # check
    if all([s >= X for s in skill]):
        ok = True
        if mincost > cost:
            mincost = cost

print(mincost if ok else -1)
import math
k=int(input())
sum=0
for i in range(1,k+1):
 for j in range(1,k+1):
  for l in range(1,k+1):
   sum=sum+(math.gcd(i,j,l))
print(sum)

### FIXED CODE ###

import math
k=int(input())
sum=0
for i in range(1,k+1):
 for j in range(1,k+1):
  a=(math.gcd(i,j))
  for l in range(1,k+1):
   sum=sum+(math.gcd(a,l))
print(sum)
from functools import reduce
N = int(input())
T = []
for _ in range(N):
    T.append(int(input()))


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def lcm(a, b):
    if b > a:
        b, a = a, b
    return int(a * b / gcd(a, b))


x = reduce(lcm, T)
print(x)


### FIXED CODE ###

from functools import reduce
N = int(input())
T = []
for _ in range(N):
    T.append(int(input()))


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def lcm(a, b):
    if b > a:
        b, a = a, b
    return a * b // gcd(a, b)


x = reduce(lcm, T)
print(x)
N,M = map(int,input().split())
S = input()
T = input()
from fractions import gcd
L = N*M//gcd(N,M)
res = ['!']*(10**10)
cnt1 = 0
for s in S:
    if cnt1*L//N > L:
        print(-1)
        exit()
    res[cnt1*L//N] = s
    cnt1 += 1
cnt2 = 0
for t in T:
    if cnt2*L//M > L:
        print(-1)
        exit()
    if res[cnt2*L//M] == '!' or res[cnt2*L//M] == t:
        res[cnt2*L//M] = t
        cnt2 += 1
    else:
        print(-1)
        exit()
print(L) 

### FIXED CODE ###

N,M = map(int,input().split())
S = input()
T = input()
from fractions import gcd
G = gcd(N,M)
if S[::N//G] == T[::M//G]:
    print(N*M//G)
else:
    print(-1)
# B - Guidebook
import numpy as np
import pandas as pd 

N = int(input())
A, B = [[], []]

for _ in range(N):
  a, b = [i for i in input().split()]
  A.append(a)
  B.append(int(b))


A = np.array(A)[:, np.newaxis]
B = np.array(B)[:, np.newaxis]
C = np.concatenate([A, B], axis=1)

print(C)
df = pd.DataFrame(C, index=[i+1 for i in range(N)])
df = df.sort_values([0, 1])
for i in df.index:
  print(i)


### FIXED CODE ###

# B - Guidebook
import numpy as np
# import pandas as pd 

N = int(input())
A, B = [[], []]

for _ in range(N):
  a, b = [i for i in input().split()]
  A.append(a)
  B.append(int(b))


A = np.array(A)[:, np.newaxis]
B = np.array(B)[:, np.newaxis].astype('int')
C = np.concatenate([A, B], axis=1)
C = C.tolist()

ans = sorted(C, key=lambda x:(x[0],-int(x[1])))

for i in ans:
  print(C.index(i)+1)


"""
df = pd.DataFrame(C, index=[i+1 for i in range(N)])
df = df.sort_values([0, 1], ascending=[True, False])
"""
# for i in df.index:
#  print(i)
N = int(input())
A = [[]]
for i in range(N):
    a = list(map(int,input().split()))
    A.append(a)
ans = 0
n = 0
while n < ((N-1)*N)//2:
    f = []
    ans += 1
    t = 0
    for i in range(1,N+1):
        if i in f:
            continue
        if len(A[i]) > 0:
            a = A[i][0]
        else:
            continue
        if (A[a][0] == i):
            if a not in f:
                A[i].pop(0)
                A[a].pop(0)
                f.append(i)
                f.append(a)
                n += 1
                t = 1
    if t == 0:
        print(-1)
        quit()
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = [0]
C = [0] 
for i in range(M):
    a,b = map(int,input().split())
    A.append(a)
    c = list(map(int,input().split()))
    x = 0
    for j in range(1,N+1):
        if j in c:
            x += 2**(j-1)
    C.append(x)
inf = 10**9
dp = [inf for i in range(2**N)]
dp[0] = 0
for i in range(1,M+1):
    dp[C[i]] = min(dp[C[i]],A[i])
    for j in range(2**N):
        k =  j|C[i]
        dp[k] = min(dp[k],dp[j]+A[i])
if dp[2**N-1] == inf:
    dp[2**N-1] = -1
print(dp[2**N-1])
a,b = map(int,input().split())

from sympy import *

x = sympy.Symbol('x') #xを変数xとして定義
f = 2*x -a-b 

solutions=sympy.solve(f,x) # f=0としてxを解き変数solutionsに代入
print(solutions)

### FIXED CODE ###

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

if (a+b)%2 == 0:
  print((a+b)//2)
else:
  print('IMPOSSIBLE')
#N = int(input())
N, M =  map(int,input().split())
#W =list(map(int,input().split()))
a = [(int(input())) for i in range(M)]

import sys
sys.setrecursionlimit(100000)

memo  =[-1]*(N+2)
memo[0] = 1
memo[1] = 1
def stair_count(n):
    for j in range(2,n+1):
        memo[j] = memo[j-1] + memo[j-2]

start = 0
answer = 1
dif = []
for i in a:
    if i == start:
        print(0)
        exit()
    else:
        n = i-1-start
        dif.append(n)
        start = i+1
stair_count(max(dif))
for i in a:
        answer = (answer * memo[n])

n = N -start
answer = answer * memo[n]
print(answer%1000000007)


### FIXED CODE ###

#N = int(input())
N, M =  map(int,input().split())
#W =list(map(int,input().split()))
a = [(int(input())) for i in range(M)]

import sys

sys.setrecursionlimit(100000)
memo  =[-1]*(N+2)
def stair_count(n):
    if memo[n]!= -1:
        return memo[n]
    if n==0 or n==1:
        memo[n] =1
        return memo[n]
    memo[n] = stair_count(n-1) + stair_count(n-2)
    return memo[n]

start = 0
answer = 1
for i in a:
        if i == start:
            print(0)
            exit()
        else:
            n = i-1-start
            answer = (answer * stair_count(n))
            start = i+1
n = N -start
answer = (answer * stair_count(n))
print(answer%1000000007)
if str(int(str(map(int,input().split())[0]) + str(map(int,input().split())[1]))**0.5).split(".")[1:][0] == "0":
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a, b = map(int,input().split())
ab = int(str(a) + str(b))
abroot = str(ab**0.5)
if abroot.split(".")[1:][0] == "0":
    print("Yes")
else:
    print("No")
A = int(input())
B = int(input())
C = int(input())
X = int(input())

count = 0
for a in A: 
    for b in B:
        for c in C:
            if 500*a + 100*b + 50*c == X:
                count += 1
    
print(count)

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
X = int(input())
res=0
for  i in range(A + 1):
    for j in range(B + 1):
        for k in range(C + 1):
            if 500*i + 100*j + 50*k == X:
                res += 1
print(res)
n = int(input())
p = list(map(int, input().split()))
answer = 0
for i in range(n):
  if p[i] + 1 != p[i + 1]:
  	answer += 1
  if answer <= 2:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
answer = 0
for i in range(n):
  if p[i]  != (i + 1):
  	answer += 1
  
if answer <= 2:
  print('YES')
else:
  print('NO')
a,b=map(int,input().split())
print(f'{a//b} {a%b} {.5:float(a/b)}')

### FIXED CODE ###

a,b=map(int,input().split())
print(a//b,a%b,f'{a/b:f}')
n = list(input().upper())
charac = []
for j in range(65,65+26):
    m= 0
    for i in range(0,len(n)):
        if ord(n[i]) == j:
            m += 1
    charac.append("{} : {}".format(chr(j),m))

for i in range(0,26):
    print(charac[i])

### FIXED CODE ###

s =""
while True:
    try:
        s += input().lower()
    except:
        break
    
s = list(map(ord,list(s)))
for i in range(ord("a"),ord("z")+1):
    print(chr(i) + " : " + str(s.count(i)))
def sum_dig(num):
    sum = 0
    while(num):
        dig = num % 10
        sum = sum + dig
        num = num // 10
#        print (dig,sum,num)
    return sum


lim, min, max = map(int, input().split(" "))
chk_sum = 0
for i in range(1,lim+1) :
    chk = sum_dig(i)
#    print(chk,type(chk))
    if (chk >= min and chk <= max) :
        chk_sum += i

print (chk_sum)


### FIXED CODE ###


a,b,c,d = map(int, input().split(" "))

if a+b < c+d :
    print("Right\n")
elif a+b > c+d:
    print("Left\n")
else :
    print("Balanced\n")
import numpy as np
[N,M] = list(map(int,input().split()))
S = list(map(int,input().split()))
T = list(map(int,input().split()))

ta = np.zeros((N+1,M+1))
ta[0,0]=1
wa = np.zeros((N+1,M+1))
wa[0,:]=1
wa[:,0]=1
output = 1
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            ta[i,j]=wa[i-1,j-1]
            wa[i,j]=wa[i-1,j]+wa[i,j-1]
        else:
            wa[i,j]=wa[i-1,j]+wa[i,j-1]-wa[i-1,j-1]
output = wa[N,M]%(10**9+7)
print(int(output))


### FIXED CODE ###

[N,M] = list(map(int,input().split()))
S = list(map(int,input().split()))
T = list(map(int,input().split()))

ta = [[0] * (M+1) for i in range(N+1)]
ta[0][0]=1
wa = [[0] * (M+1) for i in range(N+1)]
wa[0][:]=[1]*(M+1)
for i in range(N+1):
    wa[i][0]=1
output = 1
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            ta[i][j]=wa[i-1][j-1]
            wa[i][j]=(wa[i-1][j]+wa[i][j-1])%(10**9+7)
        else:
            wa[i][j]=(wa[i-1][j]+wa[i][j-1]-wa[i-1][j-1]+(10**9+7))%(10**9+7)
output = wa[N][M]
print(int(output))