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

from sys import stdin


def get_result(data):
    S = data[0]
    int_S = int(S)
    mod_all_bit = [0] * 2019
    mod_all_bit[0] = 1
    length = len(S)
    for i in range(length):
        mod = int_S % (10**(i+1)) % 2019
        mod_all_bit[mod] += 1
    ans = 0
    for val in mod_all_bit:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin


def get_result(data):
    S = data[0]
    mod_all_bit = [0] * 2019
    mod_all_bit[0] = 1
    # 10**i の mod を漸化式的に事前計算
    # こうすることで計算が効率化できる
    ten_i_mod = [0] * len(S)
    ten_i_mod[0] = 1
    for i in range(len(S)-1):
        ten_i_mod[i+1] = (ten_i_mod[i] * 10) % 2019
    mod = 0
    for i in range(len(S)):
        mod = (mod + ten_i_mod[i] * int(S[-(i+1)])) % 2019
        mod_all_bit[mod] += 1
    ans = 0
    for val in mod_all_bit:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for j in range(m):
    b, c = map(int, input().split())
    idx = bisect.bisect_left(a, c)
    if idx >= b:
        a = a[b:idx] + [c for _ in range(b)] + a[idx:]
    else:
        a = [c for _ in range(idx)] + a[idx:]
print(sum(a))


### FIXED CODE ###

import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
c = [None] * m
for j in range(m):
    c[j] = list(map(int, input().split()))
c.sort(key=lambda x: x[1], reverse=True)
k = 0
ans = 0
for i in range(n):
    if k >= m:
        ans += sum(a[i:])
        break
    if a[i] >= c[k][1]:
        ans += a[i]
    else:
        ans += c[k][1]
        c[k][0] -= 1
        if c[k][0] == 0:
            k += 1
print(ans)
### BUGGY CODE ###

import sys

if __name__ == "__main__":
    (x, y, z, k) = list(map(int, sys.stdin.readline().split()))
    a = list(map(int, sys.stdin.readline().split()))
    b = list(map(int, sys.stdin.readline().split()))
    c = list(map(int, sys.stdin.readline().split()))

    v = []
    for i in range(len(a)):
        for j in range(len(b)):
            v.append(a[i] + b[j])

    v.sort(reverse=True)

    ans = []
    for i in range(min(len(v),3000)):
        for j in range(len(c)):
            ans.append(v[i] + c[j])

    ans.sort(reverse=True)

    for i in range(k):
        sys.stdout.write("%d\n" % ans[i])

### FIXED CODE ###

import sys

if __name__ == "__main__":
    (X, Y, Z, K) = list(map(int, sys.stdin.readline().split()))
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))
    C = list(map(int, sys.stdin.readline().split()))

    v = []
    for a in A:
        for b in B:
            v.append(a + b)

    v.sort(reverse=True)

    ans = []
    for i in range(min(len(v),3000)):
        for c in C:
            ans.append(v[i] + c)

    ans.sort(reverse=True)

    for i in range(K):
        sys.stdout.write("%d\n" % ans[i])
### BUGGY CODE ###

import sys
import copy
input = sys.stdin.readline

N = int(input())
A = sorted(map(int,input().split()),reverse=True)

USED=[0]*(1<<N)
USED[0]=1

for i in range(N):
    NOW=0
    k=0
    BUSED=copy.deepcopy(USED)
    for j in range(1<<i):
        while BUSED[k]==0:
            k+=1
        while USED[NOW]==1 or A[k]<=A[NOW]:
            NOW+=1

            if NOW==1<<N:
                print("No")
                sys.exit()

        USED[NOW]=1
        k+=1


print("Yes")

### FIXED CODE ###

import sys
import copy
input = sys.stdin.readline

N = int(input())
A = sorted(map(int,input().split()),reverse=True)

USED=[0]*(1<<N)
USED[0]=1

for i in range(N):
    NOW=0
    k=0
    BUSED=copy.deepcopy(USED)
    for j in range(1<<i):
        while BUSED[k]==0:
            k+=1
        while USED[NOW]==1 or A[k]<=A[NOW]:
            NOW+=1

            if NOW==1<<N:
                print("No")
                sys.exit()

        USED[NOW]=1
        k+=1


print("Yes")
### BUGGY CODE ###

listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;
N = listA[0][0]
A = listA[1]
B = listA[2]

if sum(A) < sum(B):
    print(-1)
    exit()
C = []
for i in range(len(A)):
    num = A[i] - B[i]
    C.append(num)
change_list = [i for i in C if i < 0]
change_count = len(change_list)
if change_count == 0:
    print(0)
    exit()
max_ = 0
while True:
    change_count += 1
    max_ += max(C)
    if abs(sum(change_list)) < max_:
        break
    C[C.index(max(C))] = 0

print(change_count)

### FIXED CODE ###

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    if sum(A) < sum(B):
        return -1

    C = [a-b for a,b in zip(A,B)]
    plus = [x for x in C if x > 0]
    minus = [x for x in C if x < 0]
    change = sum(minus)
    count = 0
    if change == 0:
        return 0

    for i in sorted(plus,reverse=True):
        if change >= 0:
            break
        change += i
        count += 1
    return count + len(minus)

print(solve())
### BUGGY CODE ###

import re
import sys
s = sys.stdin.readlines()
N, Q = map(int, s[0].split())
S = s[1]
lr = list()
for i in s[2:]:
    lr.append(tuple(map(int, i.split())))
for i in lr:
    print(len(re.findall("AC", S[i[0]-1:i[1]])))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

acl = [0]*(N+1)

for i in range(N):
    acl[i+1] = acl[i] + (1 if S[i:i+2] == "AC" else 0)

for _ in range(Q):
    l, r = map(int, input().split())
    print(acl[r-1] - acl[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())#slow,行数H、列数W、爆弾数M
hcnt = [0 for i in range(H)]#何行目に何個あるか
wcnt = [0 for i in range(W)]#何列目に何個あるか
bomb = []
cnt = 0

for i in range(M):
    bh, bw = map(int, input().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append([bh - 1,bw - 1])
#hcnt [2,1]
#wcnt[1,1,1]
hmax = max(hcnt)
wmax = max(wcnt)
for i in range(H):
    for j in range(W):
        if hcnt[i] == hmax and wcnt[j] == wmax and bomb.count([i, j]) == 0:
            cnt += 1

if cnt > 0:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)

### FIXED CODE ###


import sys
from collections import Counter

H, W, M = map(int, sys.stdin.readline().rstrip().split())#行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh,bw=map(int,sys.stdin.readline().rstrip().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append((bh - 1,bw - 1))
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax = max(hcnt)#2
wmax = max(wcnt)#1

crs = 0#hmax and wmax crosspoint
for (i, j) in bomb:
    if hcnt[i] == hmax and wcnt[j] == wmax:
        crs += 1
#all crosspoint has bomb
if crs == Counter(hcnt)[hmax] * Counter(wcnt)[wmax]:
    print(hmax + wmax - 1)
#more than one crosspoint has no bomb
else:
    print(hmax + wmax)
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

count = Counter(a)
for i in a:
  ans = 0
  for j in count.items():
    
    if i == j[0]:
      ans += (j[1]-1)*(j[1]-2)//2
    else:
      ans += j[1]*(j[1]-1)//2
  print(ans)


### FIXED CODE ###

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

nums = [0]*(n+1)
for i in a:
  nums[i] += 1
  
t = 0
for j in nums:
  t += j*(j-1)//2

for k in a:
  print(t+1-nums[k])
### BUGGY CODE ###


import copy

n = int(input())
x = list(map(int, input().split(" ")))

def medianIndex(l, i):
    l.pop(i-1)
    num = len(l)
    l.sort()
    m = int((num - 1) / 2)
    print(l[m])
    

for i in range(1,n+1):
    temp = copy.copy(x)
    medianIndex(temp, i)

### FIXED CODE ###

import copy
 
n = int(input())
x = list(map(int, input().split(" ")))

y = copy.copy(x)
x.sort()
l = len(x)
m0 = x[int(l/2 - 1)]
m1 = x[int(l/2)]


for i in y:
    if i <= m0:
        print(m1)
    else:
        print(m0)
### BUGGY CODE ###

s = input()
q = int(input())
rev = 0
for i in range(q):
    qvery = input()
    if len(qvery) == 1: #t == 1
        rev += 1
    else:
        qq, f, c = qvery.split(' ')
        f = int(f)
        if rev % 2 == 0:
            if f == 1:
                s = c + s
            else:
                s = s + c
        else:
            if f == 2:
                s = c + s
            else:
                s = s + c
if rev % 2 == 1:
    s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
rev = 0
fir = ''
end = ''
for i in range(q):
    qvery = input()
    if len(qvery) == 1: #t == 1
        rev += 1
    else:
        qq, f, c = qvery.split(' ')
        f = int(f)
        if rev % 2 == 0:
            if f == 1:
                fir += c
            else:
                end += c
        else:
            if f == 2:
                fir += c
            else:
                end += c
fir = fir[::-1]
s = fir + s + end
if rev % 2 == 1:
    s = s[::-1]
print(s)
### BUGGY CODE ###

s = input()
N = int(s)
odd_num = 0
for i in range(1,N+1):
    cnt = 1
    while i // 10 >= 0:
        cnt += 1
        i //= 10
    if cnt % 2:
        odd_num += 1
print(odd_num)

### FIXED CODE ###

s = input()
N = int(s)
odd_num = 0
for i in range(1,N+1):
    cnt = 1
    num = i
    while (num // 10) > 0:
        cnt += 1
        num = num//10
    if cnt % 2:
        odd_num += 1
print(odd_num)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    INF = float('inf')
    N = int(input())
    d = [[int(x) for x in input().split()]for _ in range(N)]
    ans = 0
    for i in d:
        ans += sum(i)
    ans //= 2
    max_d = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if(i==j or j==k or i==k or d[i][j]==INF):continue
                max_d = max(max_d,d[i][j])
                if(d[i][j]>=d[i][k] + d[k][j]):
                    ans -= d[i][j]
                    d[i][j] = INF
                    d[j][i] = INF
    print(ans if ans >= max_d else -1)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    INF = float('inf')
    N = int(input())
    d = [[int(x) for x in input().split()]for _ in range(N)]
    ans = 0
    flag = True
    for i in d:
        ans += sum(i)
    ans //= 2
    max_d = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if(i==j or j==k or i==k or d[i][j]==INF):continue
                max_d = max(max_d,d[i][j])
                if(d[i][j]==d[i][k] + d[k][j]):
                    ans -= d[i][j]
                    d[i][j] = INF
                    d[j][i] = INF
                elif(d[i][j]>d[i][k] + d[k][j]):
                    flag = False
    print(ans if (ans >= max_d)and flag else -1)

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

def knapsack01rec(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0
    
    if dp[i][j] != -1:
        return dp[i][j]
    
    # start with first item
    if dp[i-1][j] == -1:
        dp[i-1][j] = knapsack01rec(n, W, weights, values, dp, i-1, j)
    
    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = dp[i-1][j]
    else:
        if dp[i-1][j-weights[i-1]] == -1:
            dp[i-1][j-weights[i-1]] = knapsack01rec(n, W, weights, values, dp, i-1, j-weights[i-1])
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
        
    return dp[i][j]

n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]
dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01rec(n, W, weights, values, dp, n, W)
print(res)

### FIXED CODE ###


def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

# dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)
### BUGGY CODE ###

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

ans = 1

for i in li:
    ans *= i
    
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
li.sort()
ans = 1

for i in li:
    ans *= i
    
    if ans > 10**18:
        print(-1)
        exit()

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

import sys
import numpy as np


def solve():
    N, K, *P = map(int, sys.stdin.read().split())
    P = np.array(P)
    n = np.convolve(P, np.ones(K), mode='valid').argmax()
    cusum = np.array(range(1000+1)).cumsum()
    return np.sum(cusum[P[n:n+K]] / P[n:n+K])


if __name__ == "__main__":
    answer = solve()
    print(answer)


### FIXED CODE ###

import sys
from itertools import accumulate


def solve():
    N, K = map(int, sys.stdin.readline().split())
    cusum_p = (0,) + tuple(accumulate(map(int, sys.stdin.read().split())))
    return (max(i - j for i, j in zip(cusum_p[K:], cusum_p[:-K])) + K) / 2


if __name__ == "__main__":
    answer = solve()
    print(answer)
### BUGGY CODE ###

from functools import reduce

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

B=[reduce(lambda a, b: a^b, A[:i]+A[(i+1):]) for i in range(N)]
[print(x) for x in B]

### FIXED CODE ###

from functools import reduce

N = int(input())
A = [int(x) for x in input().split()]
SUM=reduce(lambda a, b: a^b, A)

[print(SUM^A[i]) for i in range(N)]
### BUGGY CODE ###

from sys import stdin
import numpy as np

n,k,q = [int(x) for x in stdin.readline().rstrip().split()]
a_lst = []
p_lst = np.array([k] * n)

for i in range(q):
  a_lst.append(int(stdin.readline().rstrip()))
  
for i, a in enumerate(a_lst):
  p_lst[:a-1] -= 1
  p_lst[a:] -= 1
  
for p in p_lst:
  if p <=0:
    print('No')
  else:
    print('Yes')

### FIXED CODE ###

from sys import stdin
import numpy as np
 
n,k,q = [int(x) for x in stdin.readline().rstrip().split()]
p_lst = [k] * n
p_t_lst = [0] * n

for i in range(q):
  a = int(stdin.readline().rstrip())
  p_t_lst[a-1] += 1

p_lst = np.array(p_lst) + np.array(p_t_lst) - q

for p in p_lst:
  if p <= 0:
    print('No')
  else:
    print('Yes')
### BUGGY CODE ###

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

for i in range(k):
    if a > 0:
        a -= 1
    elif a == 0:
        if b > 0:
            b -= 1
        else:
            break
print(a,b)

### FIXED CODE ###

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

if a > k:
    a = a - k
elif (a+b) >k:
    b = (a+b)-k
    a = 0
else:
    a = 0
    b = 0
print(a,b)
### BUGGY CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
check=[-1]*n
finalans=-10**20
for i in range(n):
    if check[i]!=-1:
        continue
    loop=[i]
    now=i
    while p[now]!=i+1:
        loop.append(p[now]-1)
        now=p[now]-1
    L=len(loop)
    point=[0]*(L*2)
    point[0]=c[loop[0]]
    for j in range(1,L*2):
        if j<L:
            point[j]=point[j-1]+c[loop[j]]
        else:
            point[j]=point[j-1]+c[loop[j-L]]
    m=-10**20
    if point[L-1]>0:
        r=k%L
        if r==0:
            r=L
        for j in range(1,r+1):
            for t in range(j-1,j+L-1):
                cand=point[t]-point[t-j] if t-r>=0 else point[t]
                m=max(m,cand)
        ans=point[L-1]*(k//L)+m if r!=L else point[L-1]*((k//L)-1)+m
    else:
        for j in range(1,L+1):
            for t in range(j-1,j+L-1):
                cand=point[t]-point[t-j] if t-j>=0 else point[t]
                m=max(m,cand)
        ans=m
    finalans=max(ans,finalans)   
print(finalans)

### FIXED CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
check=[-1]*n
finalans=-10**20
for i in range(n):
    if check[i]!=-1:
        continue
    loop=[i]
    now=i
    while p[now]!=i+1:
        check[now]=1
        loop.append(p[now]-1)
        now=p[now]-1
    L=len(loop)
    point=[0]*(L*2)
    point[0]=c[loop[0]]
    for j in range(1,L*2):
        if j<L:
            point[j]=point[j-1]+c[loop[j]]
        else:
            point[j]=point[j-1]+c[loop[j-L]]
    m=-10**20
    if point[L-1]>0:
        r=k%L
        if r==0:
            r=L
        for j in range(1,r+1):
            for t in range(j-1,j+L-1):
                cand=point[t]-point[t-j] if t-j>=0 else point[t]
                m=max(m,cand)
        ans=point[L-1]*(k//L)+m if r!=L else point[L-1]*((k//L)-1)+m
    else:
        for j in range(1,L+1):
            for t in range(j-1,j+L-1):
                cand=point[t]-point[t-j] if t-j>=0 else point[t]
                m=max(m,cand)
        ans=m
    finalans=max(ans,finalans)   
print(finalans)
### BUGGY CODE ###

MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

K = int(input())
S = input()
N = len(S)

comb = Combination(N + K + 100)

ans = 0
L = 1
R = pow(26, K, MOD)
for l in range(K + 1):
    r = K - l
    ans += L * comb.nhr(N, l) * R
    ans %= MOD

    L = L * 25 % MOD
    R = R * comb.inv[26] % MOD

print(ans)


### FIXED CODE ###

MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

K = int(input())
S = input()
N = len(S)

comb = Combination(N + K + 100)

ans = 0
for l in range(K + 1):
    r = K - l
    ans += pow(25, l, MOD) * comb.nhr(N, l) * pow(26, r, MOD)
    ans %= MOD

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

from math import factorial
S=list(map(int,input()))
S.reverse()
# print(S)
count2019 = [0]*2019
mod2019 = [0]*(len(S)+1)
for i in range(len(S)):
    mod2019[i+1] =mod2019[i]+S[i]*10**i 
    mod2019[i+1]%=2019
for i in mod2019:
    count2019[i] +=1
# print(mod2019)
ans =0
for i in count2019:
    if(i>=2):
        ans += factorial(i) // factorial(i) // factorial(i - 2)
print(ans)
# print(count2019)

### FIXED CODE ###

s = list(input())
# s = list(str(10**200000))
n = len(s)
ans = 0
s.reverse()
# print(s)
x = 1
tot = 0
count = [0]*2019
for i in range(n):
    count[tot]+=1
    tot += int(s[i])*x
    # print(tot)
    tot %= 2019
    ans += count[tot]
    x = x*10%2019
print(ans)
### BUGGY CODE ###

X = int(input())
A = 1
K = 1
while K < X:
    A += 1
    K = A ** 5
S = A - 1
w = 0
while w != 1:
    P = S ** 5
    Q = P - X
    if Q < 0:
        B = 0
        while (Q != B**5):
            B -= 1
            if Q>(B**5):
                break
        if (Q == B**5):
            w += 1
        else:
            S += 1
        
    elif Q > 0:
        B = 0
        while (Q != B**5):
            B += 1
            if Q<(B**5):
                break
        if (Q == B**5):
            w += 1
        else:
            S += 1
print(S,B)

### FIXED CODE ###

X = int(input())
for i in range (240):
    for j in range (240):
        s = (i -120)**5 - (j -120)**5
        if s == X:
            A = i-120
            B = j -120
print(A,B)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
x=0
for i in range(n-1):
  for j in range(i+1,n):
    x+=A[i]*A[j]%(10**9+7)
print(x%(10**9+7))

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
sumA=sum(A)
x=0
for i in range(n-1):
  sumA-=A[i]
  x+=A[i]*sumA
print(x%(10**9+7))
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
correct_list = []

for i in range(1, n, 2):
    correct_list.append(n - i)

for i in correct_list:
    if a_list.count(i) != 2:
        print(0)
        exit()

if n % 2 != 0:
    if a_list.count(0) != 1:
        print(0)
        exit()

print(2 ** len(correct_list))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

a_dict = {}
for v in a:
    if v in a_dict:
        a_dict[v] += 1
    else:
        a_dict[v] = 1

 
if n % 2 == 0:
    possible_list = {i: True for i in range(1, n, 2)}
    for k, v in a_dict.items():
        if v != 2 or k not in possible_list:
            print(0)
            exit()
else:
    possible_list = {i: True for i in range(0, n, 2)}
    if a_dict[0] != 1:
        print(0)
        exit()
    else:
        a_dict[0] = 2
        for k, v in a_dict.items():
            if v != 2 or k not in possible_list:
                print(0)
                exit()
 
print(2 ** (n // 2) % (10 ** 9 + 7))
### BUGGY CODE ###

k = int(input())
s = '7'
cnt = 1
while 1:
  if int(s) % k == 0:
    break
  else:
    s += '7'
    cnt += 1
print(cnt)

### FIXED CODE ###

k = int(input())

t = 7
flag = True
for i in range(k):
  if t % k == 0:
    print(i + 1)
    flag = False
    break
  else:
    t = (t * 10 + 7) % k
if flag:
  print('-1')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
inputs = [int(input()) for _ in range(M)]

mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(1, N+1):
    if i in inputs:
        continue
    if i == 1:
        dp[i] = dp[i-1]
    else:
        if i - 1 not in inputs:
            dp[i] += dp[i-1]
        if i - 2 not in inputs:
            dp[i] += dp[i-2]

print(dp[-1] % mod)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
inputs = [int(input()) for _ in range(M)]

set_inputs = set(inputs)
mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(1, N+1):
    if i in set_inputs:
        continue
    if i == 1:
        dp[i] = dp[i-1]
    else:
        if i - 1 not in set_inputs:
            dp[i] += dp[i-1]
        if i - 2 not in set_inputs:
            dp[i] += dp[i-2]

print(dp[-1] % mod)