Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

#bitDP(集合を数に変換して状態(=添字)として持つようなDPのこと)
# dp[i][S]=(男性はi人目までで、既にペアになった女性の集合がSであるような場合の数)
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
mod=10*9+7
dp=[0]*(1<<n)
dp[0]=1
for i in range(1,1<<n):
    for j in range(n):
        k=bin(i).count("1")
        if i>>j&1 and a[k-1][j]:
            dp[i]=(dp[i]+dp[i^(1<<j)])%mod
print(dp[(1<<n)-1])

### FIXED CODE ###

# bitDP(集合を数に変換して状態(=添字)として持つようなDPのこと)
# dp[i][S]=(男性はi人目までで、既にペアになった女性の集合がSであるような場合の数)
# 「既にペアになった女性の集合がS」なら「bitpopcount(S)人目までをチェックした」ってことになるから、iを状態として持つ必要は無いことがわかる
import sys
input = sys.stdin.readline
mod=10**9+7
def main():
    n=int(input())
    a=[list(map(int,input().split())) for i in range(n)]
    dp=[0]*(1<<n)
    dp[0]=1
    for i in range(1,1<<n):
        k=bin(i).count("1")
        for j in range(n):
            if i>>j&1 and a[k-1][j]:
                dp[i]=(dp[i]+dp[i^(1<<j)])%mod
    print(dp[(1<<n)-1])
main()
### BUGGY CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(N-K+1):
    s = (sum(a[i:i+K])+K)/2
    ans = max(s, ans)
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a[:K])
ans = s
for i in range(N-K):
    s = s - a[i] + a[i+K]
    ans = max(s, ans)
print((ans+K)/2)
### BUGGY CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [0] * 60
  zeros = [0] * 60
  for a in A:
    for i in range(60):
      if (a >> i) & 1 == 1:
        ones[i] += 1
      else:
        zeros[i] += 1

  res = 0
  for a in A:
    for i in range(60):
      if (a >> i) & 1 == 1:
        res += zeros[i] * 2 ** i
        ones[i] -= 1
      else:
        res += ones[i] * 2 ** i
        zeros[i] -= 1
      res %= MOD
  
  print(res)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [sum(1 for a in A if a&(1<<i)) for i in range(60)]
  res = 0
  for i in range(60):
    res += ones[i] * (N - ones[i]) * ((2 ** i) % MOD)
    res %= MOD
  print(res)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import numpy as np
n = int(input())
A = list(map(int,input().split()))
q = int(input())
B = []
C = []
for _ in range(q):
    b,c = map(int,input().split())
    B.append(b)
    C.append(c)

for i in range(q):
    A = [C[i] if a == B[i] else a for a in A]
    print(sum(A))
    

### FIXED CODE ###

import numpy as np
n = int(input())
A = list(map(int,input().split()))
q = int(input())
ar = np.zeros(10**5+1)
for i in A:
    ar[i] += 1
ans = np.sum(A) 
for _ in range(q):
    b,c = map(int,input().split())
    ans = ans+ar[b]*(c-b)
    ar[c] += ar[b]
    ar[b] = 0
    print(int(ans))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

from collections import Counter

N, M = map(int, input().split())
D = 1000000000 + 7


def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac


f = primes(M)
cntr = Counter(f)

ans = 1
for k,v in cntr.items():
    ans *= combinations_count(v+N-1,v)

print(ans%D)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

# 高速 組み合わせ
def C(n, r):
  a = 1
  b = 1
  for i in range(r):
    a = a*(n-i)
    b = b*(r-i)
  return((a//b))

from collections import Counter

N, M = map(int, input().split())
D = 1000000000 + 7

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac


f = primes(M)
cntr = Counter(f)

ans = 1
for k,v in cntr.items():
    ans *= C(v+N-1,v) %D

print(ans%D)
### BUGGY CODE ###

def gcd(num1,num2):
    if num1 % num2 == 0:
        return num2
    return gcd(num2 , num1 % num2)

N = int(input())
total = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            nums = gcd(i,j)
            total += gcd(nums,k)

print(total)

### FIXED CODE ###

from math import gcd

K = int(input())

memo = []
memolist = []
for i in range(1,K+1):
    if i != 1:
        memo.append(memolist)
    memolist = []
    for j in range(1,K+1):
        memolist.append(gcd(i,j))
memo.append(memolist)

result = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            result += gcd(memo[i-1][j-1],k)

print(result)
### BUGGY CODE ###

import math
from functools import reduce

def gcd_get(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for l in range(1, K+1):
            ans += gcd_get(i, j, l)
print(ans)

### FIXED CODE ###

import math
from functools import reduce

def gcd_get(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for l in range(1, K+1):
            ans += gcd_get(i, j, l)
print(ans)
### BUGGY CODE ###

import numpy as np
A = int(input())
a = [100,101,102,103,104,105]

N = A//100
dp = np.array([np.array([0 for i in range(A+1)]) for j in range(N+1)])
dp[0][0] = 1

for i in range(N):
    for j in np.where(dp[i] == 1)[0]:
    #for j in range(A+1):
       # if dp[i][j] == 1:
        dp[i+1][j+100:j+106] = 1

print(dp[N][A])

### FIXED CODE ###

import numpy as np
A = int(input())

if A >= 3000:
    print(1)
else:
    a = [100,101,102,103,104,105]
    N = A//100
    dp = np.array([np.array([0 for i in range(A+1)]) for j in range(N+1)])
    dp[0][0] = 1

    for i in range(N):
        for j in np.where(dp[i] == 1)[0]:
        #for j in range(A+1):
           # if dp[i][j] == 1:
            dp[i+1][j+100:j+106] = 1
    print(dp[N][A])
### BUGGY CODE ###

import bisect
import numpy as np
class BinaryIndexedTree():
    def __init__(self,size):
        self.BIT = np.zeros(2*size+1,dtype=int)
    def query(self,index):
        #sum of A1 ~ Ai O(logN)
        ret=0
        while index > 0:
            ret += self.BIT[index]
            index -= index & (-index)
        return ret
    def update(self,index,x):
        #add x to Ai O(logN)
        while index <=  len(self.BIT)-1:
            self.BIT[index] += x
            index += index & (-index)
        return
n=int(input())
a=list(map(int,input().split()))
a2=sorted(a)
if n==1:print(a[0]);exit()
elif n==2:print(a[1]);exit()
ng=2*max(a)+20
ok=0
while ng-ok>1:
    check=(ok+ng)//2
    cnt=0 #check以上の要素の数
    s=np.empty(n+1,int)
    s[0]=0
    B=BinaryIndexedTree(n+1)
    for i in range(1,n+1):
        if a[i-1]<check:s[i]=s[i-1]-1
        else:s[i]=s[i-1]+1

    for i,e in enumerate(s):
        cnt += B.query(e+n+1)
        B.update(e+n+1,1)
    if cnt >= ((n+1)*n)//4:
        ok = check
    else:
        ng = check
print(ok)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a2=sorted(set(a))
L=len(a2)
if n==1:print(a[0]);exit()
elif n==2:print(a[1]);exit()
ng=L
ok=0
while ng-ok>1:
    check=a2[(ok+ng)//2]
    cnt=0 #check以上の要素の数
    idx=n
    cl=[0]*(2*n+1)
    cl[n]=1
    Ru=0
    for i in range(n):
        if a[i]<check:
            Ru-=cl[idx]-1
            idx-=1
        else:
            idx+=1
            Ru+=cl[idx]+1
        cnt += Ru
        cl[idx]+=1
    if cnt >= ((n+1)*n//2)//2:
        ok = (ok+ng)//2
    else:
        ng = (ok+ng)//2
print(a2[ok])
### BUGGY CODE ###

K, S = [int(i) for i in input().split()]
cnt = 0

for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x + y + z == S:
        cnt += 1
print(cnt)

### FIXED CODE ###

K, S = [int(i) for i in input().split()]
cnt = 0

for x in range(K+1):
  for y in range(K+1):
    candi_z = S - x - y 
    if 0<= candi_z <= K:
      cnt += 1
      

print(cnt)
### BUGGY CODE ###

s=list(input())
k=int(input())
se=set()
for i in range(len(s)+1):
  for j in range(i,len(s)+1):
    se.add(''.join(s[i:j]))
se.remove('')
l=sorted(list(se))
print(l[k-1])

### FIXED CODE ###

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

se = set()
for i in range(len(s)):
    for j in range(1,k+1):
        se.add(s[i:i+j])

li = list(se)
li.sort()
print(li[k-1])
### BUGGY CODE ###

s = input()
cnt = 0
while s.count('BW') > 0:
    cnt += s.count('BW')
    s = s.replace('BW', 'WB')
print(cnt)

### FIXED CODE ###

S = input()
cnt = 0
for i, s in enumerate(S):
    if s == 'W':
        cnt += i;
cnt -= S.count('W') * (S.count('W') - 1) // 2
print(cnt)
### BUGGY CODE ###

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

cnt = 0
for i in range(n):
    if min(p[:i+1]) == p[i]:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 1
tmp_min = p[0]
for i in range(1, n):
    tmp_min = min(tmp_min, p[i]) 
    if tmp_min == p[i]:
        cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
s = input()
num_R = sum(int(val=="R") for val in s)
num_G = sum(int(val=="G") for val in s)
num_B = sum(int(val=="B") for val in s)
total_triplets = num_R*num_G*num_B
num_missing = 0
for centre_point in range(1, n-1):
  for halfwidth in range(1, 1+min(centre_point, n-centre_point-1)):
    first_possible = s[centre_point-halfwidth] != s[centre_point]
    second_possible = s[centre_point] != s[centre_point+halfwidth]
    third_possible = s[centre_point-halfwidth] != s[centre_point+halfwidth]
    if first_possible and second_possible and third_possible: num_missing += 1
print(total_triplets-num_missing)

### FIXED CODE ###

n = int(input())
s = input()
total_triplets = sum(int(val=="R") for val in s)*sum(int(val=="G") for val in s)*sum(int(val=="B") for val in s)
num_missing = 0
for centre_point in range(1, n-1):
  for halfwidth in range(1, 1+min(centre_point, n-centre_point-1)):
    if s[centre_point-halfwidth] != s[centre_point]:
      if s[centre_point] != s[centre_point+halfwidth]:
        if s[centre_point-halfwidth] != s[centre_point+halfwidth]: num_missing += 1
print(total_triplets-num_missing)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
now = 1
ans = 0
while True:
    now = a[now-1]
    ans += 1
    if (now==2):
        print(ans)
        break
    elif (now==1):
        print(-1)
        break


### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
now = 1
ans = 0
while True:
    now = a[now-1]
    ans += 1
    if (now==2):
        print(ans)
        break
    elif (now==1):
        print(-1)
        break
    elif (ans>len(a)):
        print(-1)
        break
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
pl = [0]*n
nl = [0]*n
ans = 0

for i in range(n):
    pl[i] = i + 1 + a[i]
    nl[i] = i + 1 - a[i]

for i in range(n - 1):
    ans += nl[i + 1:].count(pl[i])

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
d = {}
ans = 0

for i in range(n):
    l = i + a[i]
    r = i - a[i]
    if l not in d:
        d[l] = 1
    else:
        d[l] += 1
    if r in d:
        ans += d[r]

print(ans)
### BUGGY CODE ###

#d
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0] * Q
C = [0] * Q
for i in range(Q):
    B[i], C[i] = map(int, input().split())
for i in range(Q):
    for j in range(A.count(B[i])):
        youso=A.index(B[i])
        A[youso]=C[i]
    print(sum(A))

### FIXED CODE ###

#d
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0] * Q
C = [0] * Q
for i in range(Q):
    B[i], C[i] = map(int, input().split())
D = [0] * (10**5+1)
ans=sum(A)
for i in A:
    D[i]+=1
for x in range(Q):
    ans+=D[B[x]]*int(C[x]-B[x])
    print(ans)
    D[C[x]]+=D[B[x]]
    D[B[x]]=0
### BUGGY CODE ###

import sys
I = lambda:map(int,sys.stdin.readline().split())
pr = lambda x:sys.stdout.write(f'{x}\n')
sys.setrecursionlimit(2000000001)
ab = abs
n = k = ar = dp = 0

def solve(x):
	global n,k,ar,dp
	if x>=n-2: return dp[x]
	if dp[x] != -1: return dp[x]
	m = 1e9
	for i in range(x+1,min(n,x+k+1)):
		t = ab(ar[x]-ar[i])+solve(i)
		m = t if t<m else m
	dp[x] = m
	# pr(f'{x} => {dp[x]}')
	return dp[x]

def main():
	global n,ar,k,dp
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [ab(ar[-2]-ar[-1]),0]
	# pr((n,k,ar,dp))
	pr(solve(0))

main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
B = []

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

result = []
stack = []

def path(start, visited):

    if len(visited) == N:
        if visited not in result:
            result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(2*M):
                if A[i] == start:
                    path(B[i], visited)
            visited.pop()

path(1, [])
print(len(result))


### FIXED CODE ###

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

result = []
stack = []

def path(start, visited):
    if len(visited) >= N:
        result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(M):
                if A[i][0] == start:
                    path(A[i][1], visited)
                if A[i][1] == start:
                    path(A[i][0], visited)
            visited.pop()

path(1, [])
result = list(map(list, set(map(tuple, result))))
print(len(result))
### BUGGY CODE ###

n,m = map(int, input().split())
lr = []
for i in range(m):
    l,r = map(int, input().split())
    lr.append((l,r))
num = 0
for h in range(1,n+1):
    t = 0
    for j in lr:
        if j[0] <= h <= j[1]:
            t += 1
        else:
            break
    if t == m:
        num += 1
print(num)

### FIXED CODE ###

n,m = map(int, input().split())
mini = 0
maxi = 10**9
for i in range(m):
    l,r = map(int, input().split())
    if mini < l:
        mini = l
    if r < maxi:
        maxi = r
t = maxi -mini + 1
if maxi < mini:
    print(0)
else:
    print(t)
### BUGGY CODE ###

s = input()
ans = 0
for i in range(len(s)-4):
    for j in range(i+4, len(s)):
        x = int(s[i:j+1])
        if x %2019 == 0:
            ans += 1
            j += 4
            if j > len(s)-1:
                break
print(ans)

### FIXED CODE ###

import collections
S = list(map(int, input()))[::-1]
mod_list = [0 for _ in range(len(S)+1)]
x = 0
d = 0
for i, s in enumerate(S):
    x += s * pow(10, d, 2019)
    d += 1
    mod_list[i] = x%2019
c = collections.Counter(mod_list)
ans = 0
for i in range(2020):
    ans += c[i] * (c[i]-1)//2
print(ans)
### BUGGY CODE ###

import bisect

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

A.sort()
C.sort()

ans = 0

for b in B:
    indexA = bisect.bisect_left(A, b)
    indexC = bisect.bisect_right(C, b)

    #print(indexA)
    #print(indexC)

    #if indexA != N-1 or indexC != 0:
    ans += len(A[0:indexA]) * len(C[indexC:N+1])

print(ans)

### FIXED CODE ###

import bisect

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

A.sort()
C.sort()

ans = 0

for b in B:
    indexA = bisect.bisect_left(A, b)
    indexC = bisect.bisect_right(C, b)

    ans += indexA * (N-indexC)

print(ans)
### BUGGY CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
c = sorted(a)
l=[1]
m=0
for i in range(n-1):
  if c[i]==c[i+1]:
    l[m]+=1 
  else:
    l.append(1)
    m+=1
x=0
p=int(len(l))
for i in range(p):
  if l[i]>=2:
    x+=l[i]*(l[i]-1)//2
for i in range(n):
  q = a.count(a[i])
  if q>=2:
    print(x-q+1)
  else:
    print(x)

### FIXED CODE ###

from collections import Counter

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

c=Counter(a)
ans=0
for i in c.keys():
  ans+=(c[i]*(c[i]-1))//2

for i in a:
  print(ans-c[i]+1)
### BUGGY CODE ###

N = int(input())
H = list(map(int,input().split()))
maxMove = 0
tempoMove = 0
for i in range(N):
  if N-len(range(i)) <= maxMove:
    break
  for j in range(N-i-1):
    if i < maxMove:
      break
    if H[i+j]>=H[i+j+1]:
      tempoMove = tempoMove + 1
    else:
      break
  if tempoMove > maxMove:
    maxMove = tempoMove
    tempoMove = 0
  else:
  	tempoMove = 0
print(maxMove)

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
maxMove = 0
tempoMove = 0
for i in range(N):
  if N-len(range(i)) <= maxMove:
    break
  if tempoMove > 0:
    tempoMove = tempoMove - 1
    continue
  for j in range(N-i-1):
    if H[i+j]>=H[i+j+1]:
      tempoMove = tempoMove + 1
    else:
      break
  if tempoMove > maxMove:
    maxMove = tempoMove
print(maxMove)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
h = tuple(map(int,input().split()))

dp = [0] + [float("inf")]*(n-1)
#print(dp)

for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[i],dp[j]+abs(h[i]-h[j]))
#print(dp)

print(dp[-1])

### FIXED CODE ###

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

dp = [float('inf') for _ in range(n)]
dp[0] = 0

for i in range(n-1):
    for j in range(1, k+1):
        if i+j <= n-1:
            temp = dp[i] + abs(l[i+j] - l[i])
            if temp < dp[i+j]:
                dp[i+j] = temp

print(dp[-1])
### BUGGY CODE ###

def main():
	N, M = map(int, input().split())
	INF = 2**30-1
	mat = [[INF for _ in range(3*N)] for _ in range(3*N)]
	for _ in range(M):
		u, v = map(int, input().split())
		mat[u-1][N+v-1] = 1
		mat[N+u-1][2*N+v-1] = 1
		mat[2*N+u-1][v-1] = 1
	for i in range(3*N):
		for j in range(3*N):
			for k in range(3*N):
				mat[j][k] = min(mat[j][k], mat[j][i]+mat[i][k])

	S, T = map(int, input().split())
	if mat[S-1][T-1] == INF:
		print(-1)
	else:
		print(mat[S-1][T-1]//3)


if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	N, M = map(int, input().split())
	INF = 2*31-1
	to = [[] for _ in range(N)]
	for _ in range(M):
		u, v = map(int, input().split())
		to[u-1].append(v-1)
	dist = [[INF, INF, INF] for _ in range(N)]

	S, T = map(int, input().split())
	queue = []
	for pos in to[S-1]:
		queue.append([pos, 1])
		dist[pos][1] = 1
	while queue:
		pos, l = queue.pop(0)
		next_positions = to[pos]
		for next_pos in next_positions:
			nl = (l+1)%3
			if dist[next_pos][nl] != INF:
				continue
			dist[next_pos][nl] = dist[pos][l]+1
			queue.append([next_pos, nl])
	ans = dist[T-1][0]
	if ans == INF:
		print(-1)
	else:
		print(ans//3)

if __name__ == '__main__':
	main()
### BUGGY CODE ###

# 2019-11-14 10:01:24(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

mod = 10 ** 9 + 7
def main():
    n, m, *broken_treads = [int(x) for x in sys.stdin.read().split()]
    safe = sorted((set(range(1, n+1)) - set(broken_treads)))

    case = []
    p_pre_pre = 0
    p_pre = 1 # 0th step
    count = 0
    continuous_broken_count = 0
    for i in range(1, n+1):
        if i in safe:
            continuous_broken_count = 0
            count += 1
            if count % 2 == 1:
                p_pre_pre = p_pre + p_pre_pre
            else:
                p_pre = p_pre_pre + p_pre
        elif count != 0:
            continuous_broken_count = 1
            if count % 2 == 1:
                case.append(p_pre_pre)
            else:
                case.append(p_pre)
            p_pre_pre = 1
            p_pre = 0
            count = 0
        else:
            continuous_broken_count += 1
            if continuous_broken_count == 2:
                print(0)
                sys.exit()
            p_pre_pre = 1
            p_pre = 0

    if count != 0:      # if n-th tread is not broken.
        if count % 2 == 1:
            case.append(p_pre_pre)
        else:
            case.append(p_pre)

    ans = 1
    for c in case:
        ans = (ans * c) % mod
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

mod = 10 ** 9 + 7
n, m, *a = [int(x) for x in sys.stdin.read().split()]

safe = sorted(set(range(1,n+1)) - set(a))
dp = [0] * (n + 2)
dp[0] = 0
dp[1] = 1
for i in safe:
    dp[i+1] = (dp[i] + dp[i-1]) % mod

print(dp[-1])
### BUGGY CODE ###

import sys

def main():
    def input():
        return sys.stdin.readline()[:-1]
    N = int(input())
    S = [ord(x) for x in input()] + [-1]
    ans = 0
    for s in range(N-1):
        for e in range(s+1,N):
            if S[s] == S[e]:
                k = 0
                while s+k < e and e+k < N and S[s+k] == S[e+k]:
                    k += 1
                    if e+k == N:
                        break
                ans = max(ans,k)
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    def input():
        return sys.stdin.readline()
    N = int(input())
    S = "_" + input()

    dp = [[0 for k in range(N+1)] for l in range(N+1)]

    for k in range(1,N):
        for l in range(k+1,N+1):
            if S[k] == S[l]:
                dp[k][l] = dp[k-1][l-1] + 1
    ans = 0
    for k in range(1,N):
        for l in range(k+1,N+1):
            if l-k >= dp[k][l]:
                ans = max(ans,dp[k][l])

    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
dic={}
for i in range(N):
    dic[i]=a.index(i+1)+1
print(*list(dic.values()), sep=" ")

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ans=[0]*N
for i in range(N):
    ans[a[i]-1]=i+1
print(*ans,sep=" ")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
 
cnt = 0
for i in range(n):
  a = l[i]
  for j, b in enumerate(l[i+1:]):
    cnt += len([c for c in l[i+j+2:] if c > a - b])
print(cnt)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
 
n = int(input())
l = [int(li) for li in input().split(' ')]
l.sort()

cnt = 0
for i in range(n):
  for j in range(i+1, n):
    cnt += bisect.bisect_left(l, l[i]+l[j])-j-1
    
print(cnt)
### BUGGY CODE ###

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

if N > K and K == 1:
    print(0)
    exit(0)

while N > abs(N - K):
    N = abs(N - K)


print(N)

### FIXED CODE ###

N,K = map(int, input().split())
ans = 0

if N < abs(N - K):
    ans = N
elif N % K == 0:
    ans = 0
else:
    ans = abs(N % K - K)


print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(int(n**0.5), n):
        if n%i == 0:
            divisors.append(i)
            divisors.append(n//i)
            break
    return divisors

s = int(input())
if s%2 == 0:
    s_1 = make_divisors(s)
    x_2 = 0
    y_1 = 0
else:
    s_1 = make_divisors(s+1)
    x_2 = 1
    y_1 = 1
x_1 = s_1[0]
y_2 = s_1[1]
x_3 = 0
y_3 = 0
print(str(x_1), str(y_1), str(x_2), str(y_2), str(x_3), str(y_3))

### FIXED CODE ###

import sys
import math
input = sys.stdin.readline

s = int(input())
if s == 10**18:
    print(0, 0, 0, 10**9, 10**9, 0)
    sys.exit()
t = math.floor(math.sqrt(s))
if t*(t+1) < s:
    x1 = t+1
    y2 = t+1
else:
    x1 = t
    y2 = t+1
x2 = 1
y1 = x1*y2 - s

print(0, 0, x1, y1, x2, y2)