Harryxun/stf_run huggingface dataset:
import itertools
import sys

N, M = map(int,input().split())

if M < N-1:
  print(0)
  sys.exit()

p = [i for i in range(N)] #0スタート
root = []

for i in range(M):
  a,b = map(int,input().split())
  root.append([a-1,b-1])

#print(root)
pattern = list(itertools.permutations(p))

ans = 0
for i in range(len(pattern)):
  Flag = [0]*N
  Flag[0] = 1
  now = 0
  last = False
  for j in range(N-1):
    if now == root[pattern[i][j]][0]:
      now = root[pattern[i][j]][1]
    elif now == root[pattern[i][j]][1]:
      now = root[pattern[i][j]][0]
    else:
      break
    if Flag[now] != 0:
      break
    else:
      Flag[now] = 1
      if j == N-2:
        last = True
  if last:
    ans += 1
print(ans)

### FIXED CODE ###

import itertools
import sys

N, M = map(int,input().split())

if M < N-1:
  print(0)
  sys.exit()

p = [i for i in range(N)] #点の数
root = []
for i in range(M):
  a,b = map(int,input().split())
  root.append((a-1,b-1))

#たどる点の順番の全探索
pattern = list(itertools.permutations(p))
#print(pattern)

ans = 0
for i in range(len(pattern)):
  if pattern[i][0] != 0:
    break
  Flag = True
  for j in range(N-1):
    if (pattern[i][j], pattern[i][j+1]) in root:
      continue
    elif (pattern[i][j+1], pattern[i][j]) in root:
      continue
    else:
      Flag = False
      break
  if Flag:
    ans += 1
print(ans)
n,m,d=int(input().split())
if d==0:
  print(1/n)
else:
  print(2*(n-d)/(n*n))

### FIXED CODE ###

n,m,d=(int(x) for x in input().split())
if d==0:
  print((m-1)/n)
else:
  print(2*(n-d)/(n*n)*(m-1))
N = int(input())
l=[]
for i in range(N):
   a,b=map(int,input().split())
   l.append((a,b))
l2=[]
for i in range(N):
   for j in range(N):
      if i!=j:
         l2.append((l[i][0]-l[j][0],l[i][1]-l[j][1]))
from collections import Counter
l2=max(Counter(l2).values())
print(N-l2)

### FIXED CODE ###

N = int(input())
l=[]
if N==1:
   print(1)
   exit()
for i in range(N):
   a,b=map(int,input().split())
   l.append((a,b))
l2=[]
for i in range(N):
   for j in range(N):
      if i!=j:
         l2.append((l[i][0]-l[j][0],l[i][1]-l[j][1]))
from collections import Counter
l2=max(Counter(l2).values())
print(N-l2)
N, M = map(int, input().split())
A = list(map(int, input().split()))
SA = sorted(A)

D = []
for _ in range(M):
  B, C = map(int, input().split())
  D += B * [C]
SD = sorted(D, reverse=True)
SD = SD[:min(N, len(SD))]

for i, s in enumerate(SA):
  if SD[i] > s:
    SA[i] = SD[i]
print(sum(SA))
  


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
#SA = sorted(A)

D = []
for _ in range(M):
  B, C = map(int, input().split())
  D.append([B, C])

SD = sorted(D, key=lambda x:x[1], reverse=True)

for b, c in SD:
  A += b * [c]
  if len(A) > N*2:
    break

SA = sorted(A, reverse=True)
#X = min(N, len(SD))
#SD = SD[:X]

print(sum(SA[:N]))
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # (x,pre_sum)
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x] + (n - X[x]) % cyc_len][1] - P[X[x]][1]
        print(pre + cyc + nxt)
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # (x,pre_sum)
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x] + (n - X[x]) % cyc_len][1] - P[X[x]][1]
        print(pre + cyc + nxt)
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)


### FIXED CODE ###

n, x, m = map(int, input().split())
mn = min(n, m)
S = set()
A = []
a = x
ans = 0
for i in range(mn):
    if a in S: break
    S.add(a)
    A.append(a)
    ans += a
    a = a*a%m
    if a == 0:
        print(ans)
        exit()

# print(S)
# print(A)
# print(len(A), n, m)
if len(A) < mn:
    st_len = 0
    while st_len < len(A) and a != A[st_len]: st_len += 1
    st = sum(A[:st_len])
    cyc_sum = sum(A[st_len:])
    cyc_len = len(A) - st_len
    cyc_num = (n - st_len) // cyc_len
    # print('m {} n {} st_len {} cyc_len {} cyc_num {}'.format(m,n,st_len,cyc_len,cyc_num))
    cyc = cyc_sum * cyc_num
    ed_len = (n - st_len) % cyc_len
    ed = sum(A[st_len:][:ed_len])
    print(st + cyc + ed)
else:
    print(ans)
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def modinv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m #負の値を返さないように

def f(n,m):
    a = 1
    for i in range(2,n+1):
        a = a*i
    return a

N = int(input())
x = list(map(int,readline().split()))

ans = 0
P = 10**9+7

b = f(N-1,P)
#print(b)

for i in range(N-1):
    l = 0
    c = modinv(N-1-i,P)
    for j in range(i,N):
        l += x[j]-x[i]
        l %= P
    #print(l)
    l = l*b%P
    l = l*c%P
    ans += l

print(ans%P)


### FIXED CODE ###

def modinv2(a,m):
    return pow(a,m-2,m)

def f(n,m):
    a = 1
    for i in range(2,n+1):
        a = a*i%m
    return a

N = int(input())
x = list(map(int,input().split()))

ans = 0
P = 10**9+7

b = f(N-1,P)

invlist = [1]

for i in range(1,N-1):
    inv = (invlist[-1]+modinv2(i+1,P))%P
    invlist.append(inv)
#print(invlist)

for i in range(N-1):
    l = x[i+1]-x[i]
    ans += (l*invlist[i]%P)*b%P

print(ans%P)
X = int(input())

ans = [0,0]
for i in range(-500,500):
  for j in range(-500,500):
    if i**5 - j**5 == X:
      ans[0] = i
      ans[1] = j
      break

ans = " ".join(map(str,ans))
print(ans)
      

### FIXED CODE ###

def nextweek(S):
  if( S == "ABC"):
    return "ARC"
  else:
    return "ABC"



S = input()
print (nextweek(S))
N,M,X = map(int,input().split())
books = [list(map(int,input().split())) for i in range(N)]
bag = []

for i in range(2**N):
  temp = []
  job = [0] * M
  for s in range(N):
    if (i>>s)&1:
      temp.append(s)
      for j in range(M):
        job[j] += item[s][j+1]
  for s in range(len(job)):
    if job[s]<X:
      break
  else:
    ans = 0
    for s in temp:
      ans += item[s][0]
    bag.append(ans)
print(min(bag) if len(bag)>=1 else -1)  

### FIXED CODE ###

# coding: utf-8
N,M,X = map(int,input().split())
item = [list(map(int,input().split())) for i in range(N)]
bag = []

for i in range(2**N):
  temp = []
  job = [0] * M
  for s in range(N):
    if (i>>s)&1:
      temp.append(s)
      for j in range(M):
        job[j] += item[s][j+1]
  for s in range(len(job)):
    if job[s]<X:
      break
  else:
    ans = 0
    for s in temp:
      ans += item[s][0]
    bag.append(ans)
print(min(bag) if len(bag)>=1 else -1)
import sys

n,k=map(int,input().split())
a=list(map(int,input().split()))
#n,k=10,10
#a=[158260522, 877914575, 602436426, 24979445,
#   861648772, 623690081, 433933447, 476190629,
#   262703497, 211047202]

if k==0:
    print(max(a))
    sys.exit()

def rf(mm):
    icnt=0
    for i in range(n):
        icnt+=(a[i]-1)//mm+1
    return icnt

asum=sum(a)
m=asum//(n+k)
um=asum
lm=1
for ii in range(100):
#    print(m,rf(m))
    if rf(m)>(n+k) :
#        print("1:",m,rf(m))
        lm=m
        m=(um+m)//2
    elif rf(m)<(n+k):
#        print("2:",m,rf(m))
        um=m
        m=(lm+m)//2
    elif rf(m)==n+k and rf(m-1)==n+k:
#        print("5:",m,rf(m))
        um=m
        m=(lm+m)//2+1
    elif rf(m)==n+k and rf(m-1)>n+k:
#        print("3:",m,rf(m))
        break
    else:
#        print("4:",m,rf(m))
        m=m-1

print(m)


### FIXED CODE ###

import sys

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

if k==0:
    print(max(a))
    sys.exit()

def rf(mm):
    if mm==0:
        mm=1
    icnt=0
    for i in range(n):
        icnt+=(a[i]-1)//mm+1
    return icnt

asum=sum(a)
m=asum//(n+k)
um=asum
lm=1
for ii in range(60):
    if m==1:
        break
    if rf(m)<=(n+k) and rf(m-1)>(n+k):
        break
    if um-lm<5:
        break
    if rf(m)>(n+k):
        lm=m
        m=(um+lm)//2-1
    elif rf(m)<(n+k):
        um=m
        m=(um+lm)//2-1
    else:
        um=m-1
        m=(um+lm)//2-1
#    if rf(m)==(n+k) and um-lm<5:

if um<1:
    print(1)
    sys.exit()
    
for mi in range(um,max(0,lm-1),-1):
    if rf(mi)<=(n+k) and rf(mi-1)>(n+k):
        break

print(mi)
n = int(raw_input()) 
G = [0 for i in range(n)] 
a = [[0 for i in range(n)] for j in range(n)]
dis = [1000 for i in range(n)]
dis[0] = 0
for i in range(n):
    G = map(int, raw_input().split())
    for j in range(G[1]):
        a[G[0]-1][G[2+j]-1] = 1
 
def bfs_visit(s):
    for k in range(n):
      if a[s][k] == 1:
       if dis[k] > dis[s] + 1:
         dis[k] = dis[s] + 1
         bfs_visit(k)

for s in range(n):
    bfs_visit(s)
for s in range(n):
    if dis[s] == 1000:
       dis[s] = -1
for s in range(n):
    print'{0} {1}'.format(s+1, d[s])
 

### FIXED CODE ###

n = int(raw_input())
   
dis = [99999 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
   
def BFS(s):
  for e in range(n):
    if v[s][e] == 1:
      if dis[e] > dis[s] + 1:
        dis[e] = dis[s]+1
        BFS(e)
   
for i in range(n):
  G = map(int, raw_input().split())
  for j in range(G[1]):
    v[G[0]-1][G[2+j]-1] = 1
   
dis[0] = 0
for s in range(n):
  BFS(s)
for s in range(n):
  if dis[s] == 99999:
    dis[s] = -1
for s in range(n):
  print'{0} {1}'.format(s+1, dis[s])
N=int(input())
list=[int(i) for i in str(input())]

x='Yes'
for i in range(N):
  if list[i]==list[i+1]:
    continue()
  elif list[i]==list[i+1]+1:
    list[i+1]=list[i+1]+1
  else:
    x='No'
    
print(x)

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
 
before = 0
result = 'Yes'
for i in range(len(h)):
    if i == 0:
        before = h[i] - 1
    else:
        if before < h[i]:
            before = h[i] - 1
        elif before == h[i]:
            before = h[i]
        else:
            result = 'No'
print(result)
import collections
import bisect
n,m=map(int,input().split())
p = [map(int,input().splilt()) for i in range(m)]
a=collections.defaultdict(list)
for x,y in sorted(p):
    a[x]+=[y]
for x,y in p:
    z=bisect.bisect(a[x],y)
    print("%06d%06d"%(x,z))

### FIXED CODE ###

import collections
import bisect
n,m=map(int,input().split())
p=[[int(j) for j in input().split()] for i in range(m)]
a=collections.defaultdict(list)
for x,y in sorted(p):
    a[x]+=[y]
for x,y in p:
    z=bisect.bisect(a[x],y)
    print("%06d%06d"%(x,z))
s = [*input()]
ans = 1000
for i in range(len(s)-2):
	x = int(s[i]+s[i+1]+s[i+2])
    if ans > abs(753-x):
      ans = abs(753-x)
print(ans)


### FIXED CODE ###

s = [s for s in input()]
ans = 1000
for i in range(len(s)-2):
    x = int(s[i]+s[i+1]+s[i+2])
    if ans > abs(753-x):
        ans = abs(753-x)
print(ans)
from numpy.linalg import solve

N = int(input())
right = list(int(x) * 2 for x in input().split())
 
left = []

for i in range(N):
    num = []
    for j in range(N):
        if j == i or j == (i + 1):
            num.append(1)
        else:
            num.append(0)
        if i == N - 1:
            num[0] = 1        
    left.append(num)

answer = ""
for a in solve(left, right):
    answer += str(int(a))
    answer += " "

print(answer)

### FIXED CODE ###

import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

N = int(input())
a_ = list(int(x) for x in input().split())
X_ = [0 for _ in range(N)]

X_sum = sum(a_)
logging.info("sum = " + str(X_sum))

X_[0] = X_sum - 2 * sum(a_[1::2])
logging.info("X_1 = " + str(X_[0]))

for i in range(1, N):
    X_[i] = 2 * a_[i - 1] - X_[i - 1]

answer = ""
for i in X_:
    answer += str(i)
    answer += " "

print(answer)
def slant(xa, ya, xb, yb):
    if ya - yb == 0:
        return 'y'
    elif xa - xb == 0:
        return 'x'
    else:
        return (ya - yb) / (xa - xb)

while True:
    try:
        xa, ya, xb, yb, xc, yc, xd, yd = map(float, input().split())
    except:
        break
    AB = slant(xa, ya, xb, yb)
    CD = slant(xc, yc, xd, yd)
    is_digit = ('x' and 'y') not in [AB, CD]

    if [AB, CD] == (['x', 'y'] or ['y', 'x']):
        print('YES')
        continue

    if is_digit:
        print('YES' if AB * CD == -1 else 'NO')
    else:
        print('NO')

### FIXED CODE ###

while True:
    try:
        xa, ya, xb, yb, xc, yc, xd, yd = map(float, input().split())
    except:
        break
    if abs((ya - yb) * (yc - yd) + (xa - xb) * (xc - xd)) < 1.e-10:
        print('YES')
    else:
        print('NO')
lines = sys.stdin.readlines()
    lines = list(map(lambda x: int(x.rstrip()), lines))
    n = lines[0]
    i = 1
    for c in range(1, n+1):
        i = lines[i]
        if i == 2:
            print(c)
            return
    print(-1)

### FIXED CODE ###

import sys
from io import StringIO
import unittest

def resolve():
    lines = sys.stdin.readlines()
    lines = list(map(lambda x: int(x.rstrip()), lines))
    n = lines[0]
    i = 1
    for c in range(1, n+1):
        i = lines[i]
        if i == 2:
            print(c)
            return
    print(-1)
    
resolve()
s=input()
s_=list(s)
i=0
while i<=len(s_)-2:
    if s_[i]!=s_[i+1]:
        del s_[i:i+2]
        i=i-1
    else:
        i+=1
print(len(s)-len(s_))

### FIXED CODE ###

s=input()
s_=list(s)
s0=s_.count("0")
s1=s_.count("1")
print(len(s)-abs(s0-s1))
M1=int(input())
D1=int(input())
M2=int(input())
D2=int(input())

dt1 = date(2019,M1,D1)
dt2 = date(2019,M2,D2)

d = dt2 - dt1
d = d.days

if d != 1:
    print(0)
else:
    if M1 == 1 and D1 == 31:
        print(1)
    elif M1 == 2 and D1 == 28:
        print(1)
    elif M1 == 3 and D1 == 31:
        print(1)
    elif M1 == 4 and D1 == 30:
        print(1)
    elif M1 == 5 and D1 == 31:
        print(1)
    elif M1 == 6 and D1 == 30:
        print(1)
    elif M1 == 7 and D1 == 31:
        print(1)
    elif M1 == 8 and D1 == 31:
        print(1)
    elif M1 == 9 and D1 == 30:
        print(1)
    elif M1 == 10 and D1 == 31:
        print(1)
    elif M1 == 11 and D1 == 30:
        print(1)
    elif M1 == 12 and D1 == 31:
        print(1)
    else:
        print(0)

### FIXED CODE ###

from datetime import date

M1,D1=map(int, input().split())
M2,D2=map(int, input().split())

dt1 = date(2019,M1,D1)
dt2 = date(2019,M2,D2)

d = dt2 - dt1
d = d.days

if d != 1:
    print(0)
else:
    if M1 == 1 and D1 == 31:
        print(1)
    elif M1 == 2 and D1 == 28:
        print(1)
    elif M1 == 3 and D1 == 31:
        print(1)
    elif M1 == 4 and D1 == 30:
        print(1)
    elif M1 == 5 and D1 == 31:
        print(1)
    elif M1 == 6 and D1 == 30:
        print(1)
    elif M1 == 7 and D1 == 31:
        print(1)
    elif M1 == 8 and D1 == 31:
        print(1)
    elif M1 == 9 and D1 == 30:
        print(1)
    elif M1 == 10 and D1 == 31:
        print(1)
    elif M1 == 11 and D1 == 30:
        print(1)
    elif M1 == 12 and D1 == 31:
        print(1)
    else:
        print(0)
from math import gcd 
n=int(input())
mod = 10**9+7
count = {}

for _ in range(n):
    a,b = map(int,input().split())
    if a==0 and b==0:
        continue
    if a*b != 0:
        g=gcd(a,b)*b//abs(b)
    elif a != 0:
        g=a
    else:
        g=b
        
    x=a//g,b//g
    count[x]=count.get(x,0)+1
        
mem=set()
ans=1
for (x,y),z in count.items():
    if (-1*x//abs(x)*y,abs(x)) in mem:
        continue
    mem.add((x,y))
    ans*=2**z+2**count.get((-1*x//abs(x)*y,abs(x)),0)-1
    ans%=mod

print((ans-1)%mod)

### FIXED CODE ###

from math import gcd 
n=int(input())
mod = 10**9+7
count = {}

num=0
for _ in range(n):
    a,b = map(int,input().split())
    if a==0 and b==0:
        num+=1
        continue
    if a*b != 0:
        g=gcd(a,b)*(b//abs(b))
    elif a != 0:
        g=a
    else:
        g=b
        
    l=a//g,b//g
    count[l]=count.get(l,0)+1
        
mem=set()
ans=1
for (x,y),z in count.items():
    if x*y==0:
        k=(y,x)
    else:
        k=(-1*x//abs(x)*y,abs(x))
    if k in mem:
        continue
    mem.add((x,y))
    ans*=(pow(2,z)+pow(2,count.get(k,0))-1)
    ans%=mod

print((ans+num-1)%mod)
n, m = map(int, input().split())
p = list()
s = list()
for i in range(m):
    a,b = input().split()
    p.append(int(a))
    s.append(b)
toi = set(p)
x = -1
ac = 0
pen = 0
check = False
for i in toi:
    for j in range(p.count(i)):
        x += 12
        if s[x] == "AC":
            if not check:
                check = True
                ac += 1
        else:
            if not check:
                pen += 1
    check = False
print(ac,pen)


### FIXED CODE ###

n,m = map(int, input().split())
ac = [False for i in range(n)]
pen = [0 for i in range(n)]
s = list()
p = list()
for i in range(m):
    a,b = input().split()
    a = int(a)
    s.append(a)
    p.append(b)
for i in range(m):
    if ac[s[i]-1] == True:
        pass
    else:
        if p[i] == "AC":
            ac[s[i]-1] = True
        else:
            pen[s[i]-1] += 1
wa = 0
for i in range(n):
    if ac[i] == True:
        wa += pen[i]
print(sum(ac), wa)
a,b,c,d = map(int,input().split())
import math
gcdcd = math.gcd(c,d)
e = a-1
print( b - b//c - b//d + b//gcdcd - e + e//c + e//d - e//gcdcd)

### FIXED CODE ###

a,b,c,d = (map(int,input().split()))
import fractions
gcdcd = c*d//int(fractions.gcd(c,d))
e = a-1
print( b - b//c - b//d + b//gcdcd - e + e//c + e//d - e//gcdcd)
a, b = map(int, input().split())
if a*b % 2 == 0:
  print('Even')
else:
  print('Odd)

### FIXED CODE ###

a, b = map(int, input().split())
if int(a*b) % 2 == 0:
    print('Even')
else:
    print('Odd')
N, M = map(int, input().split())

dic = {i:set() for i in range(1, N+1)}

for _ in range(M):
    a, b = map(int, input().split())
    dic[a].add(b)
    dic[b].add(a)


l1 = [float('inf')]*N
l1[0] = 0
ans = [0] * N
x = {1}

k1 = 1
rooms = dic[k1]

def search(k1, dic, l1, ans, x):

    if x == {i for i in range(1, N)}:
        return

    rooms = dic[k1]
    for room in rooms:
        x.add(room)
        
        if l1[k1-1] + 1 < l1[room-1]:
            l1[room-1] = l1[k1-1] + 1
            ans[room-1] = k1
            search(room, dic, l1, ans, x)



search(k1, dic, l1, ans, x)

if float('inf') in l1:
    print('No')
else:
    print('Yes')
    for n in ans[1:]:
        print(n)


### FIXED CODE ###

N, M = map(int, input().split())
A, B = [], []
dic = {i:[] for i in range(1, N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a)

node = [float('inf')] * N
node[0] = 0 #1までの距離
route = [0]*N #ランプ置く部屋
rooms = [1] #次調べる部屋
st = {1}

for r1 in rooms:
    for r2 in dic[r1]:
        if node[r1-1] + 1 <= node[r2-1]:
            node[r2-1] = node[r1-1] + 1
            route[r2-1] = r1
            if not r2 in st:
                rooms.append(r2)
                st.add(r2)
            try:
                dic[r2].remove(r1)
            except:
                continue

if float('inf') in node:
    print('No')
else:
    print('Yes')
    for i in route[1:]:
        print(i)
N, K = map(int, input().split())
H = []

for i in range(N):
        h = int(input())
        H.append(int(input()))

H.sort()

ans = []
for i in range(N-K-1):
        # print(i)
        dif = H[i+K-1] - H[i]
        ans.append(dif)

print(min(ans))
        

### FIXED CODE ###

n,k=map(int,input().split())
H=[]
for i in range(n):
    H.append(int(input()))
 
H.sort()
 
#print(H)
 
ans=H[n-1]-H[0]
 
for i in range(n-k+1):
    #print(H[i+k-1]-H[i])
    ans=min(ans,H[i+k-1]-H[i])
 
print(ans)
n, m = map(int,input().split())
data = [list(map(int,input().split())) for _ in range(m)]

s = None
for d in data:
  if s is None:
    s = set(d[1:])
  else:
    s = s & set(d[1:])
print(len(s))

### FIXED CODE ###

n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]
s = None
for d in data:
    if s is None:
        s = set(d[1:])
    else:
        s = s & set(d[1:])
print(len(s))
# B - Buildings are Colorful!

import sys
input = sys.stdin.buffer.readline

import itertools

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

if K == 1:
    print(0)
    exit()

ans = float("inf")
for visible_building_indices in list(itertools.combinations(list(range(N)), K)):
    a = original_a.copy()
    tmp = 0

    for i in range(visible_building_indices[0]):
        if a[i] >= a[visible_building_indices[i]]:
            tmp += a[i] - a[visible_building_indices[i]] + 1

    for i in range(len(visible_building_indices)-1):
        if a[visible_building_indices[i]] >= a[visible_building_indices[i+1]]:
            tmp += a[visible_building_indices[i]] - a[visible_building_indices[i+1]] + 1
            a[visible_building_indices[i+1]] = a[visible_building_indices[i]] + 1

    ans = min(ans, tmp)

print(ans)

### FIXED CODE ###

# B - Buildings are Colorful!

import sys
input = sys.stdin.buffer.readline

import itertools

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

if K == 1:
    print(0)
    exit()

ans = float("inf")
for visible_building_indices in list(itertools.combinations(list(range(N)), K)):
    a = original_a.copy()
    tmp = 0

    for i in range(len(visible_building_indices)):
        try:
            h = max([a[i] for i in range(visible_building_indices[i])])
        except:
            h = 0
        if h >= a[visible_building_indices[i]]:
            tmp += h - a[visible_building_indices[i]] + 1
            a[visible_building_indices[i]] = h + 1

    ans = min(ans, tmp)

print(ans)
import numpy as np

a,b=map(int,input().split())
c=[]
for i in range(b):
    c.append(int(input()))
c.append(a+1)    
def Fib(n):
    fib=1/np.sqrt(5)*(((1+np.sqrt(5))/2)**(n-1)-((1-np.sqrt(5))/2)**(n-1))
    return(int(fib))

d=[]
z=-1
for j in c:
    d.append(Fib(j-z))
    z=j
ans=1
for k in d:
    ans=ans*k
print(ans%1000000007)

### FIXED CODE ###

import sys

n,m=map(int,input().split())
c=set(map(int,sys.stdin))

d=[0]*(n+1)
d[0]=1
d[1]=1 if 1 not in c else 0
for j in range(2,n+1):
    if j in c:
        pass
    else:
        d[j]=(d[j-1]+d[j-2])%1000000007

print(d[n])
import math
a, b = input().split()
c = a + b
d = int(c)
e = math.sqrt(d) // 1
if d == e ** e:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import math
a, b = input().split()
c = a + b
d = int(c)
e = math.sqrt(d) // 1
if d == e * e:
    print("Yes")
else:
    print("No")
s = input()

n = len(s)
ans = []
for i in range(n):
    if s[i] != '?':
        ans.append(s[i])
    else:
        if s[i-1] == 'P' and i > 0:
            ans.append('D')
        elif s[i-1] == '?'and i > 0:
            ans.append('D')
        elif s[i+1] == '?':
            ans.append('P')
        elif s[i+1] == 'D':
            ans.append('P')
        else:
            ans.append('D')
            
print(*ans,sep = '')


### FIXED CODE ###

s = input()

n = len(s)
ans = []
for i in range(n):
    if s[i] != '?':
        ans.append(s[i])
    else:
        ans.append('D')
            
print(*ans,sep = '')
import re #与えられた条件にマッチする文字列か判定
a = input()
b = re.compile('^([^L][^R])*[^L]?$')
if match(a,b):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import re #与えられた条件にマッチする文字列か判定
a = input()
b = re.compile(r'^([^L][^R])*[^L]?$')
if b.match(a):
    print('Yes')
else:
    print('No')
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
mat = []
for _ in range(m):
    b, c = map(int, input().split())
    mat.extend([c] * b)
mat = sorted(mat, reverse=True)[:n]
for i, t in enumerate(a):
    if t < mat[i]:
        a[i] = mat[i]
    else:
        break

print(sum(a))


### FIXED CODE ###

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
bc = [[0] * 2 for _ in range(m)]
for i in range(m):
    bc[i] = list(map(int, input().split()))
bc = sorted(bc, key=lambda x: x[1], reverse=True)
mat = []
for b, c in bc:
    if len(mat) + b > n:
        mat.extend([c] * (n - len(mat)))
        break
    else:
        mat.extend([c]*b)

for i, t in enumerate(a):
    if i == len(mat):
        break
    if t < mat[i]:
        a[i] = mat[i]
    else:
        break

print(sum(a))