Harryxun/stf_run huggingface dataset:
n=input()
sn=""
for i in range(len(n)):
    sn+=str(n[i])
if int(n)%sn==0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

n=input()
sn=0
for i in range(len(n)):
    sn+=int(n[i])
if int(n)%sn==0:
    print("Yes")
else:
    print("No")
import sys, math, copy
sys.setrecursionlimit(10**8)

def main():
    n = int(input())
    x = list(input())
    for i in range(n):
        x[i] = int(x[i])
    A0 = 0
    A1 = 0
    B = sum(x)
    for i in range(n):
        A0 += x[i]*pow(2,n-i-1,B+1)
        A0 %= B+1
        if B != 0:
            A1 += x[i]*pow(2,n-i-1,B-1)
            A1 %= B-1
    for i in range(n):
        if x[i] == 0:
            BB = B + 1
            AA = A0 + pow(2,n-i-1,BB)
        else:
            BB = B - 1
            AA = A1 - pow(2,n-i-1,BB)
        ans = 1
        while AA%BB != 0:
            AA = AA%BB
            AAA = AA
            BB = 0
            while AAA != 0:
                BB += AAA%2
                AAA //= 2
            ans += 1
        print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys, math, copy
sys.setrecursionlimit(10**8)

def main():
    n = int(input())
    x = list(input())
    for i in range(n):
        x[i] = int(x[i])
    A0 = 0
    A1 = 0
    B = sum(x)
    for i in range(n):
        if B+1 != 0:
            A0 += x[i]*pow(2,n-i-1,B+1)
            A0 %= B+1
        if B-1 != 0:
            A1 += x[i]*pow(2,n-i-1,B-1)
            A1 %= B-1
    for i in range(n):
        if x[i] == 0:
            BB = B + 1
            AA = A0 + pow(2,n-i-1,BB)
        else:
            BB = B - 1
            if BB == 0:
                AA = 0
            else:
                AA = A1 - pow(2,n-i-1,BB)
        ans = 1
        if BB == 0:
            print(0)
            continue
        while AA%BB != 0:
            AA = AA%BB
            AAA = AA
            BB = 0
            while AAA != 0:
                BB += AAA%2
                AAA //= 2
            ans += 1
        print(ans)
    
if __name__ == "__main__":
    main()
S = int(input())

h = int(S/360)
rest = S % 360
m = int(rest/60)
s = rest % m

print(h:m:s)

### FIXED CODE ###

S = int(input())
h = S // 3600
m = (S % 3600) // 60
s = S % 60
print(h,m,s,sep = ":")
import sympy
N = int(input())
div_arr = sympy.divisors(N)

if len(div_arr) == 1:
    print(1)
if len(div_arr) == 2:
    ans_num = max(div_arr)
    print(len(str(ans_num)))
else:
    memo = []
    if len(div_arr) % 2 == 0:
        last_idx = -1
        count = 0
        for i in range(len(div_arr)):
            count += 1
            if N == div_arr[i] * div_arr[last_idx] and count != len(div_arr) // 2:
                last_idx -= 1
                memo.append(len(str(div_arr[last_idx])))
            else:
                break
    else:
        target_index = len(div_arr) // 2
        memo.append(len(str(div_arr[target_index])))
    print(min(memo))

### FIXED CODE ###

N = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
div_arr = make_divisors(N)

if len(div_arr) == 1:
    print(1)
elif len(div_arr) == 2:
    ans_num = max(div_arr)
    print(len(str(ans_num)))
else:
    memo = []
    if len(div_arr) % 2 == 0:
        last_idx = -1
        count = 0
        for i in range(len(div_arr)):
            count += 1
            if N == div_arr[i] * div_arr[last_idx] and count != len(div_arr) // 2:
                last_idx -= 1
                memo.append(len(str(div_arr[last_idx])))
            else:
                break
    else:
        target_index = len(div_arr) // 2
        memo.append(len(str(div_arr[target_index])))
    print(min(memo))
import math


def solve():
    S = input()
    q_count = S.count('?')
    ans = math.ceil(10 ** q_count / 13)
    if int(S.replace('?', '0')) % 13 != 0:
        ans -= 1
    if int(S.replace('?', '9')) % 13 != 0:
        ans -= 1
    if ans < 0:
        print(0)
    else:
        print(ans % (10 ** 9 + 7))


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# 解説を参考に作成
# #11254823を参考


def solve():
    S = input()
    mod = 10 ** 9 + 7

    '''
    桁数毎・余りの数字ごとのdpを作成するにあたり、mapを作る.
    たとえば新しい数字Yは前の数字Xの右側に新たに桁を作って
        Y = X(前の数字) * 10 + i(0 <= i <= 9)
    と表せる.
    この Y の余りは、
        Y % 13 = ((X % 13) * 10 + i) % 13
    と表せるので、10 * 13 のマップであらかじめ計算しておくことができる.
    このマップを以下で作っている.
        modmap[新しい桁の数字i][新しい余り(Y % 13 = k)] = 前の数字の時の余り(X % 13 = j)
    '''
    modmap = []
    for i in range(10):
        modmap.append([0] * 13)
        for j in range(13):
            k = (j * 10 + i) % 13
            modmap[i][k] = j

    # なぜ最初を1にするのか？
    # → Sの先頭に 0 を固定でつけても結果は変化しない. また付けた場合の最初の計算では余り0となる.
    # → どんなパターンでも共通の初期状態として使用できる.
    dp = [1] + [0] * 12
    for s in S:
        if s == '?':
            dp = [sum(dp[l] for l in modlist) % mod for modlist in zip(*modmap)]
        else:
            modlist = modmap[int(s)]
            dp = [dp[modlist[l]] % mod for l in range(13)]

    print(dp[5])


if __name__ == '__main__':
    solve()
a, b, c = map(int, input().split())
print("Yes" if math.sqrt(a) + math.sqrt(b) < math.sqrt(c) else "No")

### FIXED CODE ###

from decimal import *
a, b, c = map(int, input().split())
print("Yes" if Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt() else "No")
import functools
import math

N,X=map(int,input().split())
x_list=list(map(int,input().split()))
x_list.append(X)
x_list.sort()
y_list=[]
for i in range(N):
    y_list.append(x_list[i+1]-x_list[i])
z_list=list(set(y_list))
if len(z_list)==1:
    print(z_list[0])
else:
    gcd = functools.reduce(math.gcd, z_list)
    print(gcd)


### FIXED CODE ###

def gcd(m,n):
    x=max(m,n)
    y=min(m,n)
    if x%y==0:
        return y
    else:
        while x%y!=0:
            z=x%y
            x=y
            y=z
        else:
            return z


N,X=map(int,input().split())
x_list=list(map(int,input().split()))
x_list.append(X)
x_list.sort()
y_list=[]
for i in range(N):
    y_list.append(x_list[i+1]-x_list[i])
z_list=list(set(y_list))
if len(z_list)==1:
    print(z_list[0])

else:
    for i in range(len(z_list)-1):
        z_list[i+1]=gcd(z_list[i],z_list[i+1])
    print(z_list[-1])
N = int(input())

t = [0 for i in range(100001)]

for i in range(N):
    a,b = [int(i) for i in input().split(' ')]
    t[a-1] +=1
    t[b] -= 1

ans = 0

for i in range(1,100001):
    t[i] += t[i-1]
    if (t[i] > i):
        ans = i

print(ans)



### FIXED CODE ###

N = int(input())

t = [0 for i in range(100002)]

for i in range(N):
    a,b = [int(i) for i in input().split(' ')]
    t[a-1] +=1
    t[b] -= 1

ans = 0
#print(t)
for i in range(1,100002):
    t[i] += t[i-1]
    if (t[i] >= i):
        ans = i
#print(t)
print(ans)
cards = input()
cards_s = cards.split()

porker_list = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1]

alice_str = cards_s[0]
alice_int = int(alice_str)
alice = porker_list.index(alice_int)

bob_str = cards_s[1]
bob_int = int(bob_str)
bob = porker_list.index(bob_int)

if alice > bob:
    print('Alice')
elif alice == bob:
    print('Draw')
else
    print('Bob')

### FIXED CODE ###

cards = input()
cards_s = cards.split()

porker_list = ['2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '1']

alice_str = cards_s[0]
alice_s = porker_list.index(alice_str)
alice = int(alice_s)

bob_str = cards_s[1]
bob_s = porker_list.index(bob_str)
bob = int(bob_s)

if alice > bob:
    print('Alice')
elif alice == bob:
    print('Draw')
else:
    print('Bob')
x = list(map(str, input().split()))
y = list(map(str, input().split()))
z = list(map(str, input().split()))

print(''.join(x[0], y[1], z[2]))

### FIXED CODE ###

x = str(input())
y = str(input())
z = str(input())
 
s = [x[0], y[1], z[2]]

print(''.join(s))
import collections
import math
import re
import numpy


def ai():return input()#s
def a():return int(input())#a,n or k
def ma():return map(int, input().split())#a,b,c,d or n,k
def ms():return map(str, input().split())#,a,b,c,d
def lma():return list(map(int, input().split()))#x or y
def lms():return list(map(str, input().split()))#x or y
k= []
l = []
f = 0
s=0
c=0
e =1
def say(i):return print("Yes" if i == 0 else "No")
def Say(i):return print("YES" if i == 0 else "NO")
#def rep(i):return for i in range()
a = a()
x = lma()
l = set(x)
m=1
for i in l:
    if i- tn==1:
        ta = tb
        tb = tc
        tc = x.count(i+1)
    else:
        ta = x.count(i-1)
        tb = x.count(i)
        tc = x.count(i+1)
    t = ta+tb+tc
    m=max(m,t)
    tn = i
print(m)






### FIXED CODE ###

def abc072_c():
    from collections import Counter
 
    _ = int(input())
    a = list(map(int, input().split()))
    a_ex = []
    for num in a:
        a_ex.append(num)
        a_ex.append(num-1)
        a_ex.append(num+1)
 
    print(max(Counter(a_ex).values()))
 
 
abc072_c()
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from math import gcd

n,m = iim()
s = input()
t = input()
num = gcd(n,m)
lcm = n*m//num
print(lcm if s[::n//num] == t[::m//num] else -1)


### FIXED CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
#from math import gcd
from fractions import gcd
n,m = iim()
s = input()
t = input()
num = gcd(n,m)
lcm = n*m//num
print(lcm if s[::n//num] == t[::m//num] else -1)
import numpy as np

n, s = map(int, input().split())
A = list(map(int, input().split()))
DP = np.zeros(3001, dtype=np.int64)

for num, a in enumerate(A):
    double = DP * 2
    shift = np.hstack([np.zeros(a), DP[:-a]]).astype(np.int64)
    DP = double + shift
    DP[a] += 2 ** num

print(DP[s])


### FIXED CODE ###

import numpy as np

mod = 998244353

n, s = map(int, input().split())
A = list(map(int, input().split()))
DP = np.zeros(3005, dtype=np.int64)

for num, a in enumerate(A):
    double = DP * 2
    shift = np.hstack([np.zeros(a), DP[:-a]]).astype(np.int64)
    DP = double + shift
    DP[a] += pow(2, num, mod)
    DP %= mod

print(DP[s])
def mx(ls,i):
    if i == 0: return 0
    else     : return (i+1)*ls.pop()+ mx(i-1)

def cns(ls,m,sm):
    global n, s
    count = 0
    if m == n:
        if sm == s: return 1
        else      : return 0
    elif s-mx(ls,n-m+1) <= sm <= s:
        for i in range(9-m+1):
            rls = ls[:]
            k = rls.pop(i)
            count += cns(rls,m+1,sm+(m+1)*k)
        return count
    else: return 0

ls = [0,1,2,3,4,5,6,7,8,9]
while True:
    n, s = map(int, raw_input().split())
    if s > mx(n): print 0
    else        : print cns(ls,0,0)

### FIXED CODE ###

def mxmn(ls,m):
	global n
	s1,s2 = 0, 0
	for i in range(m):
		s1 += (n-i)*ls[-i-1]
		s2 += (n-i)*ls[i]
	return s1,s2

def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		mx,mn = mxmn(ls,m)
		if mx < s or mn > s: return 0
		elif mx == s or mn == s: return 1
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break
a = int(input())
if a <= 81:
    for i in range(8):
        if ((a % (i+2)) == 0) and ((a / (i+2)) <= 9):
            print("Yes")
            b = False

if b:
    print("No")

### FIXED CODE ###

a = int(input())
for i in range(1, 10):
    for j in range(1, 10):
        if i*j == a:
            print("Yes")
            exit()
print("No")
N=int(input())
flag=0
for A in range(1,10):
  for B in range(1,10):
    if N==A*B:
      flag=1
      break
 
print( "Yes" if flag == 1 else "No" )

#if flag==0:
#  print('NO')
#else:
#  print('YES')

### FIXED CODE ###

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

if A>9 or B>9:
  print(-1)
else:
  print(A*B)
def checkcheck(s):
    if s=="":
        return True
    else:
        if len(s)>=7:
            if s[-5:]=="dream" or s[-5:]=="erase":
                    s=s[:-5]
                    return checkcheck(s)
            elif s[-7:]=="dreamer":
                    s=s[:-7]
                    return checkcheck(s)
            
            elif s[-6:]=="eraser":
                    s=s[:-6]
                    return checkcheck(s) 
            else:
                s="WOW"
                return False


                
        elif len(s)==6:
            if s[-6:]=="eraser":
                return True
            else:
                return False
            
        elif len(s)==5:
            if s[-5:]=="dream" or s[-5:]=="erase":
                return True
            else:
                return False
        else:
            return False
  
s=input()
if checkcheck(s)==True:
    print("YES")
elif checkcheck(s)==False:
    print("NO")

    

### FIXED CODE ###

s=input()
length=len(s)

s=s[::-1]

s=s+"WWWWWWW"

index=0
flag=True
while index<length:
    if s[index]=="m" and s[index+1]=="a" and s[index+2]=="e" and s[index+3]=="r" and s[index+4]=="d":
        index+=5
    elif s[index]=="e" and s[index+1]=="s" and s[index+2]=="a" and s[index+3]=="r" and s[index+4]=="e":
        index+=5   
    elif s[index]=="r" and s[index+1]=="e" and s[index+2]=="m" and s[index+3]=="a" and s[index+4]=="e" and s[index+5]=="r" and s[index+6]=="d":
        index+=7   
    elif s[index]=="r" and s[index+1]=="e" and s[index+2]=="s" and s[index+3]=="a" and s[index+4]=="r" and s[index+5]=="e":
        index+=6
    else:
        flag=False
        break
if flag:
    print("YES")
else:
    print("NO")
N = int(input())
T,A = map(int,input().split())
H = list(map(int,input().split()))

Hn = [abs(A - (T - i * 0.006)) for i in H]
print(Hn.index(min(Hn)) + 1)
N = int(input())

### FIXED CODE ###

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

Hn = [abs(A - (T - i * 0.006)) for i in H]
print(Hn.index(min(Hn)) + 1)
a,b = int(input().split())

tasu = a+b
kakeru = a*b
hiku = a-b

print(max(tasu,kakeru,hiku))

### FIXED CODE ###

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

tasu = a+b
kakeru = a*b
hiku = a-b

print(max(tasu,kakeru,hiku))
import numpy as np
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

A = list(str(a))
B = list(str(b))
C = list(str(c))
D = list(str(d))
E = list(str(e))

S = []
sum = 0
if A[-1] == "0":
  sum += a
else:
  S.append(A[-1])
  sum += a + (10 - int(A[-1]))

if B[-1] == "0":
  sum += b
else:
  S.append(B[-1])
  sum += b + (10 - int(B[-1]))

if C[-1] == "0":
  sum += c
else:
  S.append(C[-1])
  sum += c + (10 - int(C[-1]))

if D[-1] == "0":
  sum += d
else:
  S.append(D[-1])
  sum += d + (10 - int(D[-1]))

if E[-1] == "0":
  sum += e
else:
  S.append(E[-1])
  sum += e + (10 - int(E[-1]))

if len(S) != "0":
  k = np.argmin(S)
  sum += int(S[k]) - 10
print(sum)

### FIXED CODE ###

import numpy as np
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

A = a % 10
B = b % 10
C = c % 10
D = d % 10
E = e % 10

S = []
sum = 0
if A != 0:
  S.append(A)
if B != 0:
  S.append(B)
if C != 0:
  S.append(C)
if D != 0:
  S.append(D)
if E != 0:
  S.append(E)
if len(S) == 0:
  sum = a + b + c + d + e
else:
  sum = (a //10 + b //10 + c //10 + d //10 + e //10)*10 + 10*(len(S) - 1) +min(S)
print(sum)
n = list(str(input()))
if n[0]==n[1]==n[2] or n[2]==n[1]==n[3]
    print("Yes")
else:
    print("No")


### FIXED CODE ###

n = input()
if n[0]==n[1]==n[2] or n[2]==n[1]==n[3]:
    print("Yes")
else:
    print("No")
N = int(input())
B =  [int(i) for i in input().split()]

A = [0] * N
sub= [0] * N
ans = 0

A[0] = B[0]
A[-1] = B[-1] 

for i in range(1, N-2):
    A[i]   = B[i]
    A[i+1] = B[i]
    if B[i] >= B[i+1]:
        A[i] = B[i-1]

if B[N-2] > B[N-1]:
    A[N-2] = B[N-3]
        
for i in range(N):
    ans = ans + A[i]

print(ans)

### FIXED CODE ###

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

A = [0] * N
sub= [0] * N
ans = 0

A[0] = B[0]
A[-1] = B[-1] 

# A[N-3]まで
for i in range(1, N-2):
    A[i] = min(B[i], B[i-1])

A[0] = B[0]
A[-1] = B[-1] 
A[N-2] = min(B[N-2], B[N-3])

for i in range(N):
    ans = ans + A[i]

print(ans)
# -*- coding: utf-8 -*-
"""
Created on Sun Nov  4 21:46:51 2018

@author: sk
"""

a = str(input())

char_list = list(a)


if a(0)==a(1):
  if a(1)==a(2):
    print("Yes")
  elif a(1)==a(3):
    print("Yes")
  else :
    print("No")

elif a(1)==a(2):
  if a(2)=a(3):
    print("Yes")
  else :
    print("No")

      
    
    
    
  
       





### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Nov  4 21:46:51 2018

@author: sk
"""

# -*- coding: utf-8 -*-
"""
Created on Sun Nov  4 21:46:51 2018

@author: sk
"""


b =str( input())

a = list(b)



if b[0]==b[1]:
  if b[1]==b[2]:
    print("Yes")
  else :
    print("No")

elif b[1]==b[2]:
  if b[2]==b[3]:
    print("Yes")
  else :
    print("No")
else:
  print("No")
list=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n=int(input())
print(list[n+1])

### FIXED CODE ###

list=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n=int(input())
print(list[n-1])
import sys
input = sys.stdin.readline
import numpy as np

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

n = I()
mylist = [list(MI()) for i in range(n-1)]

def main(j):
    time = 0
    for i in range(j,n-1):
        c, s, f = mylist[i]
        if time < s:
            time = s
        if (time - s) % f != 0:
            time += (f - (time - s) % f) #待ち時間を足す
        time += c
    print(time)
    
    
for i in range(n-1):
    main(i)
print(0)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np

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

n = I()
mylist = [list(MI()) for i in range(n-1)]

def main(j):
    time = 0
    for i in range(j,n-1):
        c, s, f = mylist[i]
        if time < s:
            time = s
        if (time - s) % f != 0:
            time += (f - (time - s) % f) #待ち時間を足す
        time += c
    print(time)
    
    
for i in range(n-1):
    main(i)
print(0)
A, B, C, K = map(int, input().split())

if A+B == K:
  print(A)
elif A+B > K:
  if a > K:
    print(K)
  else:
    print(A)
elif A+B < K:
  print(A - (K - (A+B)))


### FIXED CODE ###

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

if (A+B) == K:
  print(A)
elif (A+B) > K:
  if A > K:
    print(K)
  else:
    print(A)
elif (A+B) < K:
  print(A - (K - (A+B)))
import sys

n = int(input())
for s in range(n):
    x1,y1,x2,y2,x3,y3,x4,y4 = map(float, input().strip().split())
    angle1 = (y2-y1)/(x2-x1)
    angle2 = (y4-y3)/(x4-x3)
    if angle1 == angle2:
        print("YES")
    else:
        print("NO")

### FIXED CODE ###

N = input()
 
for n in range(N):
    data = map(float,raw_input().split( ))
    slopes = []
    for i in range(2):
        _x1 = data.pop(0)
        _y1 = data.pop(0)
        _x2 = data.pop(0)
        _y2 = data.pop(0)
         
        if _x1 != _x2:
            slopes.append((_y1 - _y2)/(_x1 - _x2))
     
    if len(slopes) == 0:
        print "YES"
    elif len(slopes) == 1:
        print "NO"
    elif abs(slopes[0] - slopes[1]) < 1e-10:
        print "YES"
    else:
        print "NO"
n = int(input())
h = list(map(int,input().split()))
ans = 0
for _ in range(100):
  streak = False
  for i in range(n):
    if h[i] > 0:
      h[i] -= 1
      if streak:
        pass
      else:
        ans += 1
        streak = True
    else:
      streak = False
print(ans)


### FIXED CODE ###

a,b,c = map(int,input().split())
print(a*b//2)
a,b,c,d=map(int,input().split())
r_ab=range(a,b+1)
count=0
for i in r_ab:
  if i%c!=0 and i%d!=0:
    count+=1
print(count)

### FIXED CODE ###

s = input()
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
  print('Bad')
else:
  print('Good')
a,b,c = input().split()
print(a+" "+b+" "+c)

### FIXED CODE ###

a,b,c = input().split(',')
print(a,b,c)
n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
for i in range(m-1):
  if A[i]+1 == A[i+1]:
    print(0)
    exit()

ANS = [A[0]-0]
for i in range(m-1):
  ANS.append(A[i+1]-A[i]-1)
ANS.append(n-A[m-1])

Fib = [1,1,2]
for i in range(3,max(ANS)+4):
  Fib.append(Fib[i-1]+Fib[i-2])

ans = 1
for i in range(len(ANS)):
  ans = (ans * Fib[ANS[i]-1])%1000000007
  
print(ans)

### FIXED CODE ###

n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
if m == 0:
  Fib = [1,2]
  for i in range(2,n):
    Fib.append(Fib[i-2]+Fib[i-1])
  print(Fib[n-1]%1000000007)
  exit()

B = [A[i+1]- A[i] for i in range(m-1)]
B.insert(0,A[0]+1)
B.append(n+1-A[m-1])

M = max(A)

Fib = [0,1]
for i in range(2,M+10):
  Fib.append(Fib[i-2]+Fib[i-1])

ans = 1
for i in range(len(B)):
  ans = (ans * Fib[B[i]-1])%1000000007
  
print(ans)
n, k = map(int, input().split())
s = map(int, input())

now = 1
cnt = 0
nums = []

for i in range(n):
    if s[i] == now: cnt+=1
    else:
        nums.append(cnt)
        now = 1 - now  # 0, 1の切り替え
        cnt = 1  # カウントを始める

if cnt != 0: nums.append(cnt)

# 計算しやすさのため、1の個数-0の個数...1の個数という配列が欲しい
if (len(nums) % 2 == 0): nums.append(0)

add = 2 * k + 1
tmp_sum = 0

left = 0
right = 0

ans = 0

for i in range(0, n, 2):

    next_right = i
    next_left = min(i + add, n)

    while left < next_left:
        tmp_sum -= nums[left]
        left++

    while right < next_right:
        tmp_sum += nums[right]
        right++

    ans = max(tmp_sum, ans)

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
s = list(map(int, input()))

now = 1
cnt = 0
nums = []

for i in range(n):
    if s[i] == now: cnt+=1
    else:
        nums.append(cnt)
        now = 1 - now  # 0, 1の切り替え
        cnt = 1  # カウントを始める

if cnt != 0: nums.append(cnt)

# 計算しやすさのため、1の個数-0の個数...1の個数という配列が欲しい
if (len(nums) % 2 == 0): nums.append(0)

add = 2 * k + 1
tmp_sum = 0

left = 0
right = 0

ans = 0

for i in range(0, len(nums), 2):

    next_left = i
    next_right = min(i + add, len(nums))

    while left < next_left:
        tmp_sum -= nums[left]
        left+=1

    while right < next_right:
        tmp_sum += nums[right]
        right+=1

    ans = max(tmp_sum, ans)

print(ans)
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    # read memo
    if memo[pos][tmp] != None: return memo[pos][tmp]
    # end
    if tmp == 0: return 1
    # next
    ret = 0
    if pos < N - 1:
        for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
    else: ret += 1
    # print("###", pos, tmp, ret)
    # write memo
    if memo[pos][tmp] != None: memo[pos][tmp] = ret
    return ret

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_max = int(math.log2(M))
memo = [[None] * (ip_max + 1) for i in range(N)] # max ip

M_tmp = M
ans = 1
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # ans update (dp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break

print(ans)

### FIXED CODE ###

# encoding: utf-8
import math
N, M = map(int, input().split())

ips = []
M_tmp = M
for p in range(2, int(math.sqrt(M)) + 1):
    if M_tmp % p > 0: continue
    for i_p in range(1, 33):
        if M_tmp % (p ** (i_p + 1)) > 0: break
    ips.append(i_p)
    M_tmp = M_tmp // (p ** i_p)
    if M_tmp == 1: break
else:
    ips.append(1)

#### O(NlogM) below ?
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    ptr_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        ptr_memo[N - 1 - j] = sum_tmp
#### O(NlogM) above ?
        
# calculate ans
ans = 1
for i_p in ips:
    ans = (ans * memo[i_p][0]) % (10 ** 9 + 7)

if M == 1: print(1)
elif ip_max < 1: print(N)
else: print(ans)