Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

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

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

from math import log2, ceil

def solve():
    n, k = MI()

    ans = 0
    m = ceil(log2(k))

    sm = 0
    v = 0
    for point in range(1, n+1):
        if 1 <= point < k:
            # さいころを振る
            # print(point)
            sm = sm + 1
            for j in range(m+1):
                point = point * 2
                # print('  j+1', j+1, point)
                if point >= k:
                    # print(j)
                    if j != 0:
                        ans = ans + 1 / (pow(2, j+1))
                    break
        else:
            # 無条件で勝利
            v = v + 1
    t = v / n
    print(ans * (1 - t) / sm + t)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

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

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n, k = MI()

    ans = 0
    for point in range(1, n+1):
        prob = 1
        while point < k:
            prob = prob / 2
            point = point * 2
        # print(point, prob)
        ans = ans + prob / n

    print(ans)

if __name__ == '__main__':
    solve()
n,m=map(int,input().split())
f=lambda x:int(x)-1
p=list(map(f,input().split()))
par=[j for j in range(n)]
def find(x):
  if x==par[x]:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
 
def union(a,b):
  ra=find(a)
  rb=find(b)
  if ra!=rb:
    par[ra]=par[ry]
 
for i in range(m):
  v,w=map(f,input().split())
  union(v,w)
 
ans=0
for j in range(n):
  if find(j)==find(p[j]):
    ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
f=lambda x:int(x)-1
p=list(map(f,input().split()))
par=[j for j in range(n)]
def find(x):
  if x==par[x]:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
 
def union(a,b):
  ra=find(a)
  rb=find(b)
  if ra!=rb:
    par[ra]=rb
 
for i in range(m):
  v,w=map(f,input().split())
  union(v,w)
 
ans=0
for j in range(n):
  if find(j)==find(p[j]):
    ans+=1
print(ans)
if A>=B and A-1>=B:
	print(A+A-1)
elif A>=B and A-1<B:
	print(A+B)
elif A<B and A<B-1:
	print(B+B-1)
else:
	print(A+B)


### FIXED CODE ###

ipt=input()
lst=ipt.split()
A=int(lst[0])
B=int(lst[1])
if A>=B and A-1>=B:
    print(A+A-1)
elif A>=B and A-1<B:
    print(A+B)
elif A<B and A<B-1:
    print(B+B-1)
else:
    print(A+B)
A = int(input())
B = int(input())
C = int(input())
K = int(input())
remain_A = K-A
if remain_A<=0:
    print(K)
else:
    remain_B = remain_A - B
    if remain_B <= 0:
        print(A)
    else:
        ans = (A*1) + (B*0) + (remain_B * (-1))
        print(ans)

### FIXED CODE ###

A,B,C,K=(int(x) for x in input().split())
remain_A = K-A
if remain_A<=0:
    print(K)
else:
    remain_B = remain_A - B
    if remain_B <= 0:
        print(A)
    else:
        ans = (A*1) + (B*0) + (remain_B * (-1))
        print(ans)
n, k = map(int, input().split())
d = collections.defaultdict(int)
b = map(int, input().split())
for e in b:
    d[e] += 1
ret = 0
a = sorted([v for v in d.values()], reverse = True)
while len(a) > k:
    ret  += a.pop()
print(ret)

### FIXED CODE ###

import collections
n, k = map(int, input().split())
d = collections.defaultdict(int)
b = map(int, input().split())
for e in b:
    d[e] += 1
ret = 0
a = sorted([v for v in d.values()], reverse = True)
while len(a) > k:
    ret  += a.pop()
print(ret)
n,a=int(input())
print(n*n-a)

### FIXED CODE ###

n=int(input())
a=int(input())
print(n*n-a)
N, K = map(int, input().split())
p_list = list(map(int, input().split()))

#そのサイコロの期待値の合計
e_list = []
for i in range(N):
    e_list.append((1+p_list[i])/2.0)

#累積和
s_list = []
for i in range(N):
    s_list.append(sum(e_list[:i+1]))

#隣接するk個の和
for i in range(N-K+1):
    s_sum = s_list[i+K-1] - s_list[i]
    if dst < s_sum:
        dst = s_sum
print(dst)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

#期待値L
L = [0 for _ in range(N)]
for i in range(N):
    L[i] = (1+P[i])/2

#累積和S
S = [0 for i in range(N)]
S[0] = L[0]
for i in range(1, N):
    S[i] = S[i-1] + L[i]

total = S[K-1]
for i in range(N-K):
    tmp = S[i+K]-S[i]
    if total < tmp:
        total = tmp

print(total)
n, k = map(int, input().split())
hp_list = list(map(int, input().split()))
hp_list.sort()

attack = 0
for i, hp in enumurate(reversed(hp_list)):
  if i < k:
    continue
  attack += hp
print(attack)

### FIXED CODE ###

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

attack = 0
for i, hp in enumerate(reversed(hp_list)):
  if i < k:
    continue
  attack += hp
print(attack)
L, R = list(map(int, input().split()))

if (R-L) > 2018:
    print(0)
else:
    mini = 2019
    for i in range(R-L):
        mini = min(mini, (L+i)*(L+i+1)%2019)
print(mini)


### FIXED CODE ###

L, R = list(map(int, input().split()))

if (R-L) > 2018:
    print(0)
else:
    mini = 2019
    for i in range(L,R):
        for j in range(i+1,R+1):
            mini = min(mini, (i*j)%2019)
    print(mini)
from collections import deque
inf=float("inf")

import numpy as np
def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="#":
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for X in range(max(0,x-3),min(h,x+3)):
            for Y in range(max(0,y-3),min(w,y+3)):
                if color[X][Y]!="black":
                    D[X][Y]=min(D[X][Y],D[x][y])
                    if color[X][Y]=="white":
                        queue.append([X,Y])
                    color[X][Y]="gray"
        color[x][y]="black"

    return D


def Check():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if D[i][j]==inf:
                color[i][j]="black"

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if D[i][j]==0 and color[i][j]=="white":
                queue.append([i,j])
                while len(queue)>0:
                    x,y=queue.popleft()
                    for a,b in [[1,0],[0,1],[0,-1],[-1,0]]:
                        X,Y=x+a,y+b
                        if 0<=X<h and 0<=Y<w:
                            if color[X][Y]=="white":
                                color[X][Y]="gray"
                                queue.append([X,Y])
                    color[x][y]="black"
                point +=1

    return point


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
ans=True if D[G[0]-1][G[1]-1]!=inf else False
if ans==False:print(-1);exit()
print(Check()-1)

### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
inf=float("inf")


def BFS():
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque()
    queue.append([Cx-1,Cy-1,0])
    D[Cx-1][Cy-1]=0

    while len(queue)>0:
        x,y,cnt=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if S[X][Y]=="." and D[X][Y]>cnt:
                    D[X][Y]=cnt
                    queue.appendleft([X,Y,cnt])

        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if S[X][Y]=="." and D[X][Y]>cnt+1:
                    D[X][Y]=cnt+1
                    queue.append([X,Y,cnt+1])

    return D[Dx-1][Dy-1]


h,w=map(int,input().split())
Cx,Cy=map(int,input().split())
Dx,Dy=map(int,input().split())
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)
import numpy as np
def solve(stdin):
    from heapq import heapify,heapreplace

    n,m = stdin[:2]
    A = stdin[2:2+n].tolist()
    BC = stdin[2+n:].reshape(-1,2)

    heapify(A)

    BC = sorted(BC,key=lambda x:(x[1]),reverse=True)
    for b,c in BC:
        if c<A[0]:
            break
        for i in range(b):
            if A[0]>c:
                break
            heapreplace(A,c)
        
    #print(A)
    return sum(A)
 
def main():
    
    stdin = np.fromstring(open(0).read(), dtype=np.int64, sep=' ')
    print(solve(stdin))
 
def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
 
if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    A = list(map(int,input().split()))
    BC = [list(map(int,input().split())) for _ in range(m)]

    BC = sorted(BC,key=lambda x:(x[1]),reverse=True)
    append_list = []
    for b,c in BC:
        if len(append_list)>=n:
            break
        append_list+=[c]*b
    A+=append_list
    A.sort(reverse=True)
    print(sum(A[:n]))
if __name__=='__main__':
    main()
bingo = []
for i in range(3):
    array = list(map(int, input().strip().split()))
    bingo.append(array)

N = int(input())
number = []

for j in range(N):
    number.append(int(input()))

result = []
for n in range(N):
    for t in range(3):
        for y in range(3):
            if(bingo[t][y] == number[n]):
                result.append([t,y])

bingo_a = 'No'
for r in range(len(result)):
    for t in range(3):
        t_a = 0
        for y in range(3):
            if(result[r][0] == t or result[r][1] == y):
                t_a = t_a + 1
        if(t_a == 3):
            bingo_a = 'Yes'

for r in range(len(result)):
    for y in range(3):
        y_a = 0
        for t in range(3):
            if(result[r][0] == t or result[r][1] == y):
                y_a = y_a + 1
        if(y_a == 3):   
            bingo_a = 'Yes'

ans = 0
for rr in range(len(result)):
    if(result[rr][0] == 0 or result[rr][1] == 0):
        ans = ans + 1
    if(result[rr][1] == 1 or result[rr][1] == 1):
        ans = ans + 1
    if(result[rr][0] == 2 or result[rr][1] == 2):
        ans = ans + 1
if(ans == 3):
    bingo_a = 'Yes'

ans = 0
for rr in range(len(result)):
    if(result[rr][0] == 0 or result[rr][1] == 2):
        ans = ans + 1
    if(result[rr][1] == 1 or result[rr][1] == 1):
        ans = ans + 1
    if(result[rr][0] == 2 or result[rr][1] == 0):
        ans = ans + 1
if(ans == 3):
    bingo_a = 'Yes'

print(bingo_a)
print(result)

### FIXED CODE ###

N = int(input())
print(int(N / 2 + 0.5))
def dfs(node, distance, ans, G):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance+edge_size) % 2)
            dfs(next_node, distance+edge_size, ans, G)
    return ans


N = int(input())

G = [[] for i in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    G[u-1].append([v-1, w])
    G[v-1].append([u-1, w])

ans = [-1]*N
ans = dfs(0, 0, ans, G)
print(*ans, sep='\n')


### FIXED CODE ###

import sys
sys.setrecursionlimit(20000000)
#input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    u-=1;v-=1
    g[u].append([v,w])
    g[v].append([u,w])
ans = [-1]*n
def dfs(x,y):
    for i,j in g[x]:
        if ans[i] == -1:
            ans[i] = (y+j)%2
            dfs(i,y+j)
dfs(0,0)
for i in ans:
    print(i)
A,B=list(map(int,input.split()))
print((A-1)*(B-1) + 1)

### FIXED CODE ###

A,B=list(map(int,input().split()))
print((A-1)*(B-1))
get = map(int, input().split())
a = get[0]
b = get[1]
if a <= b:
  print(str(a) * b)
elif a > b:
  print(str(b) * a)

### FIXED CODE ###

get = list(map(int, input().split()))
a = get[0]
b = get[1]
if a <= b:
  print(str(a) * b)
elif a > b:
  print(str(b) * a)
S = input()
T = input()
if (T.startsadwith(S)) and len(T) == (len(S) + 1):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

S = input()
T = input()
if (T.startswith(S)) and len(T) == (len(S) + 1):
    print('Yes')
else:
    print('No')
N,S = map(int,input().split())
n,s = map(int,input().split())
T = int(input())

if (N - n)%(S-s)== 0 and N + S*T >= n + s*t:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

A,V = map(int,input().split())
B,W = map(int,input().split())
T = int(input())

dis = abs(B - A)
speed = V - W


if dis <= speed*T:
  print("YES")
else:
  print("NO")
# ABC 155 C
import numpy as np
N = int(input())
S = [str(input()) for i in range(N)]
S = np.array(S)

uni, count = np.unique(S, return_counts=True)
max_list = np.argwhere(count==np.max(count))
for index in max_list:
    print(uni[index][0])

### FIXED CODE ###

# ABC 155 C
from collections import Counter
import numpy as np
N = int(input())
S = [str(input()) for i in range(N)]
S = np.array(S)

count = Counter(S)
max_num = max(count.values())
max_list = [i for i,j in count.items() if j==max_num]

max_list.sort()
print('\n'.join(max_list))
K,A,B=map(int,input().split())
K1=K-(A+1)
n=K1//2
print(max(K+1,((n+1)*B-n*A+K1%2)))
#
K,A,B=map(int,input().split())
print(A+((K-A+1)//2)*(B-A)+(K-A+1)%2) if(B-A>2 and K-A>0) else print(K+1)
#
k,a,b = map(int,input().split())
if a+2 > b:
    print(k+1)
else:
    print(a-1 + (b-a)*(k-a+1)//2 + (k-a+1)%2)

### FIXED CODE ###

k,a,b = map(int,input().split())
if a+2 > b:
    print(k+1)
else:
    print(a + (b-a)*((k-a+1)//2) + (k-a+1)%2)
import collections
n=int(input())
a,b,c,d=[],[],[],[]
for i in range(n):
    b.append([])
for i in range(n-1):
    a.append(list(map(int,input().split())))
for i in range(n-1):
    j=0
    d.append(a[i][0])
    d.append(a[i][1])
    while True:
        if j not in b[a[i][0]-1] and j not in b[a[i][1]-1]:
            c.append(j)
            b[a[i][0]-1].append(j)
            b[a[i][1]-1].append(j)
            break
        j+=1
print(collections.Counter(d).most_common()[0][1])
for i in range(n-1):
    print(c[i]+1)


### FIXED CODE ###

a=['SUN','MON','TUE','WED','THU','FRI','SAT']
print(7-a.index(input()))
a = int(input())
b = int(input())
c = int(input())

1 < a, b, c < 100
if a == b == c:
    print(1)
else:
    if a != b != c:
        print(3)
    else:
        print(2)

### FIXED CODE ###

a, b, c = map(int, input().split())
print(len(set([a, b, c])))
n = map(int,input().split())

for i in n:
  if n[i] == 1:
    n[i]=9
  elif n[i] == 9:
    n[i]=1
print(''.join(n))

### FIXED CODE ###

n = input()
ans = 0
for i in range(3):
  if n[i] == '1':
    ans += 10**(2-i) * 9
  else:
    ans += 10**(2-i) * 1
print(ans)
def dfs(n):
        divide=["dream","erase","eraser","dreamer"]
        if n==len(s):
                return True
        for i in divide:
                if n+len(i)<=len(s):
                        if s[n:n+len(i)]==i:
                                if dfs(n+len(i)):
                                        return True

        return False
s=input()
print("YES") if dfs(0) else print("NO")


### FIXED CODE ###

s=input().replace("eraser",",").replace("erase",",").replace("dreamer",",").replace("dream",",").replace(",","")
print("YES" if s=="" else "NO")
import numpy as np
X, Y, A, B, C = map(int,input().split())
Reds = list(map(int, input().split()))
Greens = list(map(int, input().split()))
Ns = list(map(int, input().split()))

Reds = np.array(Reds)
Greens = np.array(Greens)
Ns = np.array(Ns)

Reds = np.sort(Reds)[:X-1:-1]
Greens = np.sort(Greens)[:Y-1:-1]
Ns = np.sort(Ns)[::-1]

Full = np.append(Reds, Greens)
Full = np.append(Full, Ns)
Full = np.sort(Full)[::-1]

sum = 0

for i in range(X+Y):
    sum += Full[i]

print(sum)

### FIXED CODE ###

import numpy as np
X, Y, A, B, C = map(int,input().split())
Reds = list(map(int, input().split()))
Greens = list(map(int, input().split()))
Ns = list(map(int, input().split()))

Reds = np.array(Reds)
Greens = np.array(Greens)
Ns = np.array(Ns)

Reds = np.sort(Reds)[::-1]
Greens = np.sort(Greens)[::-1]
Ns = np.sort(Ns)[::-1]

Full = np.append(Reds[:X], Greens[:Y])
Full = np.append(Full, Ns)
Full = np.sort(Full)[::-1]

sum = 0

for i in range(X+Y):
    sum += Full[i]

print(sum)
n,k = map(int, input().split())
m = 1000000007
ans = []
for i in range(1,n+2):
    ans_min = (0+(i-1))*i*0.5
    ans_max = ((n+1-i)+n)*i*0.5
    ans.append(ans_max-ans_min+1)
ans_wa = [ans[0]]
for i in range(1,n+1):
    ans_wa.append(ans_wa[i-1]+ans[i])
print(int((ans_wa[n]-ans_wa[k-2])%m))

### FIXED CODE ###

import math
r = int(input())
print(r*math.pi*2)
n, m = map(int, input().split())
#リスト内包表記でaに入れる
a = [int(input()) for _ in range(m)]

#MODに'1000000007'を入れる
MOD = 10**9 + 7
#zに集合を作成する
z = set(a)
 
#i段目までにたどりつく方法を順に求める
x = [0 for _ in range(n + 1)]
#0段目の場合1とする
x[0] = 1
#1段目の場合は集合の中に1が含まれていないかどうか、含まれていない:1、含まれている:0
x[1] = int(1 not in z)
#2段目以降の場合
for i in range(2, n + 1):
#集合の中にiが含まれていない場合
    if i not in z:
#i段目に1段か2段で上ってきた経路数を足して、MODで割る、dp[i]に蓄積する
        x[i] = (x[i - 1] + x[i - 2]) % MOD
print(x[i])

### FIXED CODE ###

n, m = map(int, input().split())
#リスト内包表記でaに入れる
a = [int(input()) for _ in range(m)]

#MODに'1000000007'を入れる
MOD = 10**9 + 7
#zに集合を作成する
z = set(a)
 
#i段目までにたどりつく方法を順に求める
x = [0 for _ in range(n + 1)]
#0段目の場合1とする
x[0] = 1
#1段目の場合は集合の中に1が含まれていないかどうか、含まれていない:1、含まれている:0
x[1] = int(1 not in z)
#2段目以降の場合
for i in range(2, n + 1):
#集合の中にiが含まれていない場合
    if i not in z:
#i段目に1段か2段で上ってきた経路数を足して、MODで割る、dp[i]に蓄積する
        x[i] = (x[i - 1] + x[i - 2]) % MOD
print(x[n])
import sys
n,y = map(int, input().split())

for a in range(n+1):
	for b in range(n+1-a):
	  if (a * 10000 + b * 5000 + (n-a-b) * 1000 == y):
		print(str(a) + ' ' + str(b) + ' ' + str(c))
		sys.exit()

print('-1 -1 -1')
sys.exit()

### FIXED CODE ###

import sys

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

for a in range(n+1):
	for b in range(n+1-a):
		c = n - a - b
		if (a * 10000 + b * 5000 + c * 1000 == y):
				print(str(a) + ' ' + str(b) + ' ' + str(c))
				sys.exit()
	
print('-1 -1 -1')
sys.exit()
s = list(input())
t = list(input())

if(t in s):
    print(0)

result = []
for i in range(len(s) - len(t)):
    result.append(len(t))
    for j in range(len(t)):
        if(s[i+j] == t[j]):
            result[i] -= 1

print(min(result))



### FIXED CODE ###

s = list(input())
t = list(input())

if(t in s):
    print(0)

result = [0] * ((len(s) - len(t)) + 1)
for i in range(len(s) - len(t) + 1):
    result[i] = len(t)
    for j in range(len(t)):
        if(s[i+j] == t[j]):
            result[i] -= 1
 
print(min(result))
N = int(input())
D = int(input())

if (N%(2*D-1)==0):
  print(N//(2*D-1))
else:
  print(N//(2*D-1) + 1)

### FIXED CODE ###

N, D = tuple([int(i) for i in input().split(" ")])

if (N%(2*D+1)==0):
  print(N//(2*D+1))
else:
  print(N//(2*D+1) + 1)
print(int(input)**3)

### FIXED CODE ###

print(int(input())**3)
# -*- coding: utf-8 -*-
N = int(input())
A = [int(v) for v in input().split(' ')]

# 負の数が偶数 -> 全部+にできる
# 負の数が奇数 -> どれか一つが-になる
# 負の数の偶奇チェック
sign = 1
for a in A:
    sign *= a/abs(a)

abs_A = [abs(a) for a in A]

if sign > 0:
    print(sum(abs_A))
else:
    print(sum(abs_A)-min(abs_A))

### FIXED CODE ###


N = int(input())
A = [ int(v) for v in input().split() ]

if N < 2 and 1e5 < N: raise()
for v in A:
    if v < -1e9 and v < 1e9: raise()

abs_list = [abs(v) for v in A]

total = sum( abs_list )
num_of_minus = sum([ True for v in A if v < 0 ])

if num_of_minus % 2 == 1:
    print(total - min( abs_list ) * 2)
else:
    print(total)
import math

nk = list(map(int, list(input().split())))

n = nk[0]
k = nk[1]

countSplit = 1
countPut = n - k + 1

for i in range(k):
    if i == 0:
        print(n - k + 1)
    elif i <= n - k:

        countSplit = int(countSplit * (k - i) / i)
        countPut = int(countPut * (n - k + 1 - i) / (i + 1))
        
        print((countPut * countSplit) % (10 ** 9 + 7))

    else:
        print(0)

### FIXED CODE ###

import math

nk = list(map(int, list(input().split())))

n = nk[0]
k = nk[1]

countSplit = 1
countPut = n - k + 1

for i in range(k):
    if i == 0:
        print(n - k + 1)
    elif i <= n - k:

        countSplit = math.factorial(k - 1) // math.factorial(k - 1 - i) // math.factorial(i)
        countPut = math.factorial(n - k + 1) // math.factorial(n - k - i) // math.factorial(i + 1)
        """
        countSplit = int(countSplit * (k - i) / i)
        countPut = int(countPut * (n - k + 1 - i) / (i + 1))
        """
        print((countPut * countSplit) % (10 ** 9 + 7))

    else:
        print(0)
a, b, c = [int(i) for i in input().split()]
for i in range(2, b+1):
    if a*i % b == c:
        print("YES")
        break
    else:
        print("NO")



### FIXED CODE ###

a, b, c = input().split()
if a[-1] == b[0] and b[-1] == c[0]:
    print("YES")
else:
    print("NO")
input_arr = [int(x) for x in input().split()]
 
L = input_arr[0]
R = input_arr[1]
 
min_ans = 10**18
for i in range(L,R):
    for j in range(i+1,R+1):
        if (i*j)%2019 < min_ans:
            min_ans = ans
print(min_ans)


### FIXED CODE ###

L,R = [int(x) for x in input().split()]
 
min_ans = 10**18

if R-L>=2019:
  min_ans=0
else:
  for i in range(L,R):
      for j in range(i+1,R+1):
          ans = (i*j)%2019

          if ans < min_ans:
              min_ans = ans
          if min_ans == 0:
              break
print(min_ans)
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())

s=[a,b,c,d,e,k]

if s[5]-s[0] <= s[6]:
  print("Yay!")
else:
  print(":(")

### FIXED CODE ###

a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())

if e-a <= k:
  print("Yay!")
else:
  print(":(")
t = list(input())
for i in range(len(t)):
  if t[i] == '?':
    if i == 0:
      if t[1] == 'P':
        t[i] = 'D'
      else:
        t[i] = 'P'
    if i == len(t)-1:
        t[i] = 'D'
    else:
      if t[i-1] == 'P':
        t[i] = 'D'
      else:
        if t[i+1] == 'P':
          t[i] = 'D'
        else:
          t[i] = 'P'
a = ''
for i in range(len(t)):
  a += t[i]
        
print(a)

### FIXED CODE ###

t = list(input())    
for i in range(len(t)):

  if t[i] == '?':
    if len(t) == 1:
      if t[i] == '?':
        t[i] = 'D'
      break
    if i == 0:
      if t[1] == 'P':
        t[i] = 'D'
      else:
        t[i] = 'P'
    if i == len(t)-1:
        t[i] = 'D'
    else:
      if t[i-1] == 'P':
        t[i] = 'D'
      else:
        if t[i+1] == 'P':
          t[i] = 'D'
        else:
          t[i] = 'P'
a = ''
for i in range(len(t)):
  a += t[i]
        
print(a)