Harryxun/stf_run huggingface dataset:
# coding: utf-8
import time
import re
import math
import fractions

def main():
    N,K=map(int,input().split())
    for i in range(1,K+1):
        if N-K+1-i>0:
            l=math.factorial(N-K+1)/(math.factorial(i)*math.factorial(N-K+1-i))
            r=math.factorial(K-i+i-1)/(math.factorial(K-i)*math.factorial(i-1))
            print(int(l*r%1e9))
        else:
            print(1)
start=time.time()
main()
#print("処理速度 {}sec".format(time.time()-start))
#A=list(map(int,input().split()))
#A,B,C=map(int,input().split())
#n=int(input())
# global N,A,B,C,D,memo,mx,mn,temp

### FIXED CODE ###

# coding: utf-8
import re
import math
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)

def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 

 
#main

N,blue=map(int,input().split())
fac=fac_list(N,mod)
red=N-blue
for a in range(1,blue+1):
    if red+1<a:
        num=0
    else:
        num=fac[red+1]*pow(fac[red+1-a]*fac[a],mod-2,mod)
        num*=fac[blue-(a-1+1)+a-1]*pow(fac[blue-(a-1+1)]*fac[a-1],mod-2,mod)
    print(num%mod)
from collections import deque
import math


def main():
    n = int(input())
    digits = deque()
    alpha = ord('a') - 1
    maxex = int(math.log(n-1, 26))
    ex = 1
    zflag = False
    for ex in range(1, maxex + 2):
        bb = pow(26, ex - 1)
        aa = bb * 26
        rem = n % aa // bb
        n -= bb * rem
        if rem == 0:
            if n == 0:
                break
            rem += 26
            n -= aa
        digits.appendleft(chr(alpha + rem))

    [print(d, end='') for d in digits]
    print()


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque
import math


def main():
    n = int(input())
    if n == 1:
        print('a')
        return
    digits = deque()
    alpha = ord('a') - 1
    maxex = int(math.log(n-1, 26))
    ex = 1
    for ex in range(1, maxex + 2):
        bb = pow(26, ex - 1)
        aa = bb * 26
        rem = n % aa // bb
        n -= bb * rem
        if rem == 0:
            if n == 0:
                break
            rem += 26
            n -= aa
        digits.appendleft(chr(alpha + rem))

    [print(d, end='') for d in digits]
    print()


if __name__ == '__main__':
    main()
import heapq

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

pq = []

for ab in abs:
  a,b = ab[0],ab[1]
  heapq.heappush(pq, tuple(b,a))
  
dl = 0
tt = 0

ans = "Yes"

for i in range(n):
  ba = pq.pop()
  dl += ba[0]
  tt += ba[1]
  if dl > tt:
    ans = "No"
    break
print(ans)

### FIXED CODE ###

import heapq

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

pq = []

for ab in abs:
  a,b = ab[0],ab[1]
  heapq.heappush(pq, tuple([b,a]))
  
dl = 0
tc = 0

ans = "Yes"

for i in range(n):
  ba = heapq.heappop(pq)
  dl = ba[0]
  tc += ba[1]
  if dl < tc:
    ans = "No"
    break
print(ans)
import sys

sys.setrecursionlimit(10**7)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
l = [1] * 3
for i in range(k):
    d = ni()
    a = na()
    for i in range(d):
        l[a[i] - 1] = 0
print(sum(l))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
l = [1] * n
for i in range(k):
    d = ni()
    a = na()
    for i in range(d):
        l[a[i] - 1] = 0
print(sum(l))
a, b = int(input())

if a > b:
    print('a > b')

if a < b:
    print('a < b')

if a == b:
    print('a == b')



### FIXED CODE ###

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

if a > b:
    print('a > b')
elif a < b:
    print('a < b')
else:
    print('a == b')
if a < b:
  print"a < b"
elif a > b:
  print"a > b"
elif a == b:
  print"a == b"

### FIXED CODE ###

a, b = map(int, input().split())
if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
n = list(a, b, c, d, e)

n.sort(key=lambda x: x % 10)

for i in range(1, 5):
    n[i] = 10 * (n[i]//10+1)

sm = sum(n)
print(sm)


### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
n = [a, b, c, d, e]

zr = list(filter(lambda x: x % 10 == 0, n))
nz = list(filter(lambda x: x % 10 != 0, n))

nz.sort(key=lambda x: x % 10)

for i in range(1, len(nz)):
    nz[i] = 10 * (nz[i]//10+1)

print(sum(nz)+sum(zr))
import fractions
import math
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
tmp_sum = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      tmp_list = [i,j,k]
      tmp_sum += gcd_list(tmp_list)
print(tmp_sum)

### FIXED CODE ###

K = int(input())
import math
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
tmp_sum = 0
for i in range(1,K+1):
  for j in range(i,K+1):
    for k in range(j,K+1):
      if i != j and j != k:
        tmp_list = [i,j,k]
        tmp_sum += gcd_list(tmp_list)*6
      elif i == j and j == k:
        tmp_list = [i,j,k]
        tmp_sum += gcd_list(tmp_list)
      else:
        tmp_list = [i,j,k]
        tmp_sum += gcd_list(tmp_list)*3
print(tmp_sum)
n = int(input())
h = list(map(int, input().split()))
cnt = n 
h.reverse()
for i in h:
    for j in h:
    	if h[j]>h[i]:
    		h.remove(h[i])
    		cnt = cnt-1
    	else:
    		h.remove(h[i])
else:
    print(cnt)

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
max_mount = h[0]
ans = 0 
for i in range(n):
    if max_mount<=h[i]:
    	ans +=1
    	max_mount = h[i]
print(ans)
import math
a, b, x = map(int, input().split())
s = x / a
if s > a * b / 2:
  rad = math.atan(a ** 3 / (2 * a * a * b - 2 * x))
  print(90 - (rad * 180 / math.pi))
else:
  rad = math.atan(a * b * b / (2 * x))
  print(rad * 180 / math.pi)

### FIXED CODE ###

import math
a, b, x = map(int, input().split())
s = x / a
if s > a * b / 2:
  if x == a * a * b:
    print(0)
  else:
    rad = math.atan(a ** 3 / (2 * a * a * b - 2 * x))
    print(90 - (rad * 180 / math.pi))
else:
  rad = math.atan(a * b * b / (2 * x))
  print(rad * 180 / math.pi)
def visit(u):
    global color, d, f, t
    color[u] = GRAY
    d[u] += t
    t += 1
    for v in range(n):
        if (M[u-1][v-1] == 0):
            continue
        if (color[v] == WHITE):
            visit(v)
    color[u] = BLACK
    f[u] = t
    t += 1

n = int(input())
M = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    temp = list(map(int, input().split()))
    for i in range(temp[1]):
        M[temp[0]-1][temp[i+2]-1] = 1

WHITE = 0
GRAY = 1
BLACK = 2
color, d, f = [WHITE for i in range(n)]
t = 1
for u in range(n):
    if (color[u] == WHITE):
        visit(u)
for u in range(n):
    print(str(u+1), str(d[u]), str(f[u]), sep = " ")

### FIXED CODE ###

def dfs(u):
    global dfs_color, d, f, t
    color[u] = GRAY
    d[u] += t
    t += 1
    for v in range(n):
        if (M[u][v] == 0):
            continue
        else:
            if (color[v] == WHITE):
               dfs(v)
    color[u] = BLACK
    f[u] = t
    t += 1

n = int(input())
M = [[False for i in range(n)] for j in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(tmp[1]):
        M[tmp[0]-1][tmp[j+2]-1] = True

WHITE = 0
GRAY = 1
BLACK = 2
color = [WHITE for i in range(n)]
d = [0 for i in range(n)]
f = [0 for i in range(n)]
t = 1

for u in range(n):
    if (color[u] == WHITE):
        dfs(u)
for u in range(n):
    print(str(u+1), str(d[u]), str(f[u]), sep = " ")
import math
X=int(input())
if X=2:
  print(X)
else:
  for i in range(math.sqrt(X)-1):
    if X%(2+i)==0:
      X+=1
    else:
      print(X)

### FIXED CODE ###

import math
X=int(input())
while True:
    for i in range(2,int(math.sqrt(X))+1):
      if X%i==0:
        X+=1
        break
    else:
      print(X)
      break
N, T = map(int, input().split())
C = []
for i in range(N):
  c, t = map(int, input().split())
  if t <= T:
    C.append(c)
C.sort()
print(C[0])

### FIXED CODE ###

N, T = map(int, input().split())
C = []
for i in range(N):
  c, t = map(int, input().split())
  if t <= T:
    C.append(c)
if len(C) >= 1:
  C.sort()
  print(C[0])
else:
  print('TLE')
# coding: utf-8
a, b, k = map(int, input().split())

mi = min(a, b)
c = 0
for i in range(1, mi):
    if a%i == 0 and b%i == 0:
        c += 1
    if c == k:
        break
print(i)

### FIXED CODE ###

# coding: utf-8
a, b, k = map(int, input().split())

mi = min(a, b)
c = 0
for i in range(mi+1, 0, -1):
    if a%i == 0 and b%i == 0:
        c += 1
    if c == k:
        break
print(i)
N = int(input())
D = list(map(int, input().split()))

D = sorted(D)
max_ = max(D)
min_ = min(D)

middle_idx = len(D)//2

diff = D[middle_idx+1] - D[middle_idx]
print(diff)

  
  
  
  

### FIXED CODE ###

N = int(input())
D = list(map(int, input().split()))
 
D = sorted(D)
max_ = max(D)
min_ = min(D)

middle_idx = len(D)//2
 
diff = D[middle_idx] - D[middle_idx-1]
print(diff)
if a+b <= 2*c:
    print(a*x+b*y)
else:
    if x>=y:
        if a <= 2*c:
            print(y*(2*c)+a*(x-y))
        else:
            print(2*c*x)
    else:
        if b<= 2*c:
            print(x*2*c+b*(y-x))
        else:
            print(2*c*y)

### FIXED CODE ###

a,b,c,x,y = map(int,input().split())


if a+b <= 2*c:
    print(a*x+b*y)
else:
    if x>=y:
        if a <= 2*c:
            print(y*(2*c)+a*(x-y))
        else:
            print(2*c*x)
    else:
        if b<= 2*c:
            print(x*2*c+b*(y-x))
        else:
            print(2*c*y)
import sys
input = sys.stdin.readline

data = int(input())
E = [[] for _ in range(data)]
for _ in range(data-1):
  a, b, c = list(map(int, input().split()))
  E[a-1].append((b-1,c))
  E[b-1].append((a-1,c))

nim, mike = list(map(int, input().split()))

queue = [mike-1]
dist = [None]*data
dist[K-1] = 0
while queue:
  queue_new = []
  for q in queue:
    for e in E[q]:
      if dist[e[0]] is not None: continue
      dist[e[0]] = dist[q] + e[1]
      queue_new.append(e[0])
  queue = queue_new

for _ in range(nim):
  x, y = list(map(int, input().split()))
  print(dist[x-1]+dist[y-1])

### FIXED CODE ###

# solution

data=int(input())

abc=[list(map(int,input().split())) for _ in [0]*(data-1)]

q,k=map(int,input().split())

array1=[list(map(int,input().split())) for _ in [0]*q]

k-=1

tree=[[] for _ in [0]*data]

dist=[-1]*data

dist[k]=0

[tree[a-1].append([b-1,c]) for a,b,c in abc]

[tree[b-1].append([a-1,c]) for a,b,c in abc]

q=[k]

while(q):
	qq=[]
	for i in q:
		for j,k in tree[i]:
			if dist[j]<0:
				dist[j]=dist[i]+k
				qq.append(j)
	q=qq

for x,y in array1:
	print(dist[x-1]+dist[y-1])
ref = "0123456789ACDEFGHIJKLMNOPQRSTUVWXYZ"
while 1:
    N,M,Q = map(int,raw_input().split())
    if N == 0: break
    sn = set(range(N))
    corr = [set(range(N)) for _ in range(M)]
    s = [0]*N
    for loop in xrange(Q):
        S,B = raw_input().split()
        s = [1-s[i] if S[i] == "1" else s[i] for i in range(N)]
        on  = set([i for i in range(N) if s[i]])
        off = sn-on
        for i in range(M):
            corr[i] &= on if B[i] == "1" else off
    ans = [ref[list(i)[0]] if len(i) == 1 else "?" for i in corr]
    print "".join(ans)

### FIXED CODE ###

ref = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
while 1:
    N,M,Q = map(int,raw_input().split())
    if N == 0: break
    sn = set(range(N))
    corr = [set(range(N)) for _ in range(M)]
    s = [0]*N
    for loop in xrange(Q):
        S,B = raw_input().split()
        s = [1-s[i] if S[i] == "1" else s[i] for i in range(N)]
        on  = set([i for i in range(N) if s[i]])
        off = sn-on
        for i in range(M):
            corr[i] &= on if B[i] == "1" else off
    ans = [ref[list(i)[0]] if len(i) == 1 else "?" for i in corr]
    print "".join(ans)
N = int(input())

def count(start, end):
  return end - start + 1

keta = 1
while True:
  if 10**keta > N:
    break
  else:
  	keta += 1
      
num = 0
for k in range(1, keta+1):
  if k % 2 == 1:
    num += count(10**(k-1), min(N, 10**k-1))

print(num)

### FIXED CODE ###

A, B, C = list(map(int, input().split()))
 
ABgap = A - B
remain = max(0, C - ABgap)
 
print(remain)
a = input()
if len(a) == 0:
    print("WA")
    exit()
if a[0] == "A":
    b = 0
    for i in range(1, len(a)):
        if a[i] == "C" and (1 < i < len(a) - 1):
            b += 1
        else:
            if a[i] != a[i].lower():
                print("WA")
                exit()
if b == 1:
    print("AC")
else:
    print("WA")

### FIXED CODE ###

a = input()
b = 0
if a[0] != "A":
    print("WA")
    exit()
for i in range(2,len(a)-1):
    if b == 0 and a[i] == "C":
        b = i
    elif b != 0 and [i] == "C":
        print("WA")
        exit()
if b == 0:
    print("WA")
    exit()
for i in range(len(a)):
    if i != 0 and i != b and a[i].isupper():
        print("WA")
        exit()
print("AC")
N, K  = (int(i) for i in input().split())
D = 0
for i in range(N + 1):
    for j in range(N + 1):
         A = i + j
         if A % K == 0:
              for j in range(N + 1):
                  for k in range(N + 1):
                      B = j + k
                      C = i + k
                      if B % K = 0 and C % K = 0:
                          D += 1
print(D)

### FIXED CODE ###

K = int(input())
if K % 2 == 0:
    A = (K // 2) * (K // 2)
    print(A)
else:
    B = ((K // 2) + 1) * (K // 2)
    print(B)
a = map(str, input().split())
b=0
if a[0]="1":
  b+=1
else if a[1]="1":
  b+=1
else if a[2]="1":
  b+=1
print(b)
  


### FIXED CODE ###

a = str(input())
b=0
if a[0]=="1":
  b+=1
if a[1]=="1":
  b+=1
if a[2]=="1":
  b+=1
print(b)
count = 0
target = raw_input()

while True:
  sentence = raw_input()
  if raw_input == 'END_OF_TEXT':
    break
  words = sentence.split()
  for word in words:
    if word == target:
      count +=1

print count

### FIXED CODE ###

count = 0
target = raw_input()

while True:
  sentence = raw_input()
  if sentence == 'END_OF_TEXT':
    break
  words = sentence.lower().split()
  for word in words:
    if word == target:
      count +=1

print count
n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
bc = [list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)

ad = 0
idx = 0
for b, c in bc:
    for i in range(b):
        if a[idx+i] < c:
            ad += c
        else:
            idx += i
            print(ad + sum(a[idx:]))
            exit()
    else:
        idx += i+1
print(ad + sum(a[idx:]))

### FIXED CODE ###

n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
bc = [list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)

ad = 0
idx = 0
for b, c in bc:
    for i in range(min(b, n-idx)):
        if a[idx+i] < c:
            continue
        else:
            ad += c*i
            idx += i
            print(ad + sum(a[idx:]))
            exit()
    ad += c*min(b, n-idx)
    idx += min(b, n-idx)
print(ad + sum(a[idx:]))
S = include()
a = "Sunny"
b = 'Cloudy'
c = 'Rainy'
if S == a:
    print(b)
    elif S == b:
        print(c)
    elif S == b:
        print(a)
else
exit()

### FIXED CODE ###

import sys
S = input()
a = "Sunny"
b = 'Cloudy'
c = 'Rainy'
if S == a:
    print(b)
elif S == b:
        print(c)
elif S == c:
        print(a)
else:
    sys.exit()
sys.exit()
n = int(input())
a = list(map(int, input().split()))

nega = sorted(list(filter(lambda x: x < 0, a)))
posi = sorted(list(filter(lambda x: x >= 0, a)), reverse=True)

selected = []

for i in range(n - 1):
  if len(nega) == 0:
    (x, y) = posi[0], posi[-1]
    posi = posi[1:-1]
    selected.append((x, y))
    nega.append(x - y)
  elif len(posi) == 0:
    (x, y) = nega[0], nega[-1]
    nega = nega[1:-1]
    selected.append((x, y))
    posi.append(x - y)
  else:
    if len(nega) >= len(posi):
      (x, y) = posi.pop(), nega.pop()
      selected.append((x,y))
      posi.append(x - y)
    else:
      (x, y) = nega.pop(), posi.pop()
      selected.append((x, y))
      nega.append(x - y)

if len(nega) == 1:
  print(nega[0])
else:
  print(posi[0])

for (x, y) in selected:
  print(f'{x} {y}')


### FIXED CODE ###

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

a.sort()

posi = [a[-1]]
nega = [a[0]]

for n in a[1:-1]:
  if n < 0:
    nega.append(n)
  else:
    posi.append(n)

selected = []
ans = nega[0]

for n in posi[1:]:
  (x, y) = ans, n
  ans = x - y
  selected.append((x, y))

nega.append(ans)

ans = posi[0]
for n in nega[1:]:
  (x, y) = ans, n
  ans = x - y
  selected.append((x, y))

print(ans)

for (x, y) in selected:
  print(str(x) + ' ' + str(y))
a⁵-b⁵=(a-b)(a⁴+a³b+a²b²+ab³+b⁴)
def main():
  X = int(input())
  
  a = -1
  b1 = -1
  b2 = +1
  while True:
    a += 1
    while True:
    	b1 += 1
        b2 -= 1
        if (X/(a-b1)).is_integer():
          if int(X/(a-b1)) == a**4 + b1*(a**3) + (a**2)*(b1**2) + a*(b1**2) + b1**4:
            print("{} {}\n".format(a, b1))
            return 0
          
        if (X/(a-b2)).is_integer():
          if int(X/(a-b2)) == a**4 + b2*(a**3) + (a**2)*(b2**2) + a*(b2**2) + b2**4:
            print("{} {}\n".format(a, b2))
            return 0
          
          
if __name__ == "__main__":
  main()
         
          

### FIXED CODE ###

def main():
    X = int(input())

    a = -1
    
    while True:
        b1 = 0
        b2 = 0
        while b1 < a:
            
            if (X/(a-b1)).is_integer():
                if int(X/(a-b1)) == a**4 + b1*(a**3) + (a**2)*(b1**2) + a*(b1**3) + b1**4:
                    print("{} {}\n".format(a, b1))
                    return 0

            if (X/(a-b2)).is_integer():
                if int(X/(a-b2)) == a**4 + b2*(a**3) + (a**2)*(b2**2) + a*(b2**3) + b2**4:
                    print("{} {}\n".format(a, b2))
                    return 0

            b1 += 1
            b2 -= 1
            
        a += 1


if __name__ == "__main__":
    main()
from operator import mul
from functools import reduce

def com(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def run():
  N = int(input())
  K = int(input())
  Nnum = len(str(N))
  #1
  all1 = com(Nnum, K)*9**K
  #2
  all2 = (9-int(str(N)[0]))*com(Nnum-1, K-1)*9**(K-1)
  if K == 1:
    print(all1-all2)
  #3
  elif K == 2:
    all3 = 0
    for n in range(1, Nnum):
      N2 = int(str(N)[n])
      if N2 != 0:
        all3 += 9-N2
        break
      all3 += 9
    else:
      all3 = (Nnum-1)*9
    print(all1-all2-all3)
  #4
  else:
    all3 = 0
    count = 0
    for n in range(1, Nnum):
      N2 = int(str(N)[n])
      if N2 != 0:
        if count == 0:
          all3 += (9-N2)*com(Nnum-n-1, 1)*9
        elif count == 1:
          all3 += 9-N2
        count += 1
        if count == 2:
          break
      elif count == 0:
        all3 += 9*(Nnum-n-1)*9
      else:
        all3 += 9
    else:
      all3 = (Nnum-1)*9
    print(all1-all2-all3)
    
  

if __name__ == '__main__':
    run()

### FIXED CODE ###

def run():
  N = list(map(int, list(input())))
  K = int(input())
  Nlen = len(N)
  dp = [[[0]*(K+2) for _ in range(2)] for n in range(Nlen+1)]
  dp[0][0][0] = 1
  for nlen in range(Nlen):
    dN = N[nlen]
    for d in range(10):
      for j in range(2):
        for k in range(K+2):
          flagj = j or d < dN
          if (flagj == 0) and (d > dN): continue
          flagk = min(K+1, k+(d != 0))
          dp[nlen+1][flagj][flagk] += dp[nlen][j][k]
  print(dp[-1][0][K]+dp[-1][1][K])
  
if __name__ == '__main__':
    run()
N, M = [int(i) for i in input().split(' ')]
SC = []
for _ in range(M):
    SC.append([int(i) for i in input().split(' ')])

ch = [-1] * N
for s,c in SC:
    if N >1:
        if s == 1 and c == 0:
            print(-1)
            exit()

    if ch[s-1] == -1 or ch[s-1] == c:
        ch[s-1] = c
    else:
        print(-1)
        exit()
s = 10**(N-1) if N >1 else 0
f = 10 ** N if N >1 else 10
for n in range(s,f):
    n = list(str(n))
    flg = 0
    for s,c in SC:
        if not n[s-1] == str(c):
            flg = 1

    if flg == 0:
        print(''.join(n))
        exit()

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, M, K = map(int, input().split())

def dfs(v):
    size = 1
    for w in fr[v]:
        if ~roots[w]: continue
        roots[w] = roots[v]
        size += dfs(w)
    return size

fr = defaultdict(set)
for _ in range(M):
    a, b = [int(x) -1 for x in input().split()]
    fr[a].add(b)
    fr[b].add(a)
bl = defaultdict(set)
for _ in range(K):
    a, b = [int(x) - 1 for x in input().split()]
    bl[a].add(b)
    bl[b].add(a)

roots = [-1] * N
sizes = [-1] * N

for v in range(N):
    if ~roots[v]: continue
    roots[v] = v
    sizes[v] = dfs(v)

ans = []
for v in range(N):
    w = roots[v]
    res = sizes[w] - len(fr[v]) - sum(1 for u in bl[v] if roots[u] == w) -1
    ans.append(res)

print(*ans)
x=int(input())
for i in range(x):
	num=[int(i) for i in input().split()]
	b=[]
	c=[]
	flag=0
	b.append(num[0])
	c.append(int(0))
	for i in range(1,10):
		if b[0]<num[i]:
			b.append(num[i])
		elif c[0]<num[i]:
			c.append(num[i])
		else:
			flag=1
			break
	if flag==:
		print("YES")
	else:
		print("No")


### FIXED CODE ###

x=int(input())
for _ in range(x):
	num=list(map(int,input().split()))
	b,c=0,0
	flag=True
	for i in num:
		if b<i:
			b=i
		elif c<i:
			c=i
		else:
			print("NO")
			flag=False
			break
	if flag:
		print("YES")
a,b = input().split()

if a>b:
    print("a > b")
else if a==b:
    print("a == b")
else:
    print("a < b")


### FIXED CODE ###

a,b = input().split()
a = int(a)
b = int(b)
if a>b:
    print("a > b")
elif a==b:
    print("a == b")
else:
    print("a < b")
import fractions
a,b,c,d = map(int,input().split())	
lcm = c * d // fractions.gcd(c, d)
#print(lcm)
def divisor(x):
	
	x_c = fractions.floor(x/c)
	x_d = fractions.floor(x/d)
	#print(x_c,x_d)
	x_lcm = fractions.floor(x/lcm)
	#print(x_c,x_d,x_lcm)
	return x-x_c-x_d+x_lcm
#print(divisor(b),divisor(a))
ans = divisor(b)-divisor(a-1)
print(ans)

### FIXED CODE ###


import fractions
a,b,c,d = map(int,input().split())	
lcm = c * d // fractions.gcd(c, d)
#print(lcm)
def divisor(x):
	
	x_c = x//c
	x_d = x//d
	#print(x_c,x_d)
	x_lcm = x//lcm
	#print(x_c,x_d,x_lcm)
	return x-x_c-x_d+x_lcm
#print(divisor(b),divisor(a))
ans = divisor(b)-divisor(a-1)
print(ans)