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

import math
import copy
from copy import deepcopy
import sys
import fractions
from functools import reduce
import heapq
 
# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)
 
# ===FUNCTION===
 
def getInputInt():
    inputNum = int(input())
    return inputNum
 
 
def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]
 
    return outputData
 
 
def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)
 
    return outputDataList
 
 
def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)
 
    return outputDataList
 
 
# ===CODE===
 
n = getInputInt()
data = getInputListInt()
l = len(data)
 
ans = []
 
for i in range(l-1, -1, -1):
    cnt = 0
    for j in ans:
        if j % (i+1) == 0:
            cnt += 1
    if data[i] != cnt % 2:
        ans.append(i+1)
 
if len(ans) == 0:
    print(0)
else:
    print(len(ans))
    print(*ans, sep=" ")
 

### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    b = [0 for i in range(n)]
    ans = []

    for i in range(n // 2, n):
        if a[i] == 1:
            b[i] = a[i]
            ans.append(i + 1)

    for i in range(n // 2 - 1, -1, -1):
        cnt = 0
        for j in range(i * 2 + 1, n, i + 1):
            cnt ^= b[j]
        if cnt != a[i]:
            b[i] = 1
            ans.append(i + 1)

    tmp = len(ans)
    print(tmp)
    if tmp > 0:
        print(*ans, sep=" ")


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

n, k = map(int, input().split())
lr = []
for _ in range(k):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        lr.append(i)
lr = set(lr)
lr = sorted(lr)
dp = [0] * (n + 1)
dp[n] = 1
for i in range(n, 1, -1):
    for step in lr:
        if step <= i:
            dp[i - step] += dp[i] % 998244353
            dp[i - step] %= 998244353
        else:
            break
print(dp[1])

### FIXED CODE ###

n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]
mod = 998244353

dp = [0] * n
dp[0] = 1

acc = 0

for i in range(1, n):
    for l, r in lr:
        if i - l >= 0:
            acc += dp[i - l]
            acc %= mod
        if i - r - 1 >= 0:
            acc -= dp[i - r - 1]
            acc %= mod
        dp[i] = acc

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

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

def my_index_multi(l, x):
  return [i for i, _x in enumerate(l) if _x == x]

for i in range(Q):
  BC = list(map(int, input().split()))
  B_i = BC[0]
  C_i = BC[1]
  B_ind = my_index_multi(A, B_i)
  for j in B_ind:
    A[j] = C_i
  print(sum(A))
  
  

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
dic = dict()
 
for i in A:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1
 
ans = sum(A)
 
for i in range(Q):
    b, c = list(map(int, input().split()))
    x = 0
    if b in dic:
        x = dic.pop(b)
        if c in dic:    
            dic[c] += x
        else:
            dic[c] = x
    ans += x * (c-b)
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""
import bisect
n, m, qn = list(map(int, input().split()))

lr = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    li, ri = list(map(int, input().split()))
    lr[li][ri] += 1
lrac = [[0]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    ac = 0
    for j in range(n+1):
        ac += lr[i][j]
        lrac[i][j] = ac

for i in range(qn):
    pi, qi = list(map(int, input().split()))
    ans = 0
    for i in range(pi, qi+1):
        ans += lrac[i][qi] - lrac[i][pi-1]
    
    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""

n, m, qn = list(map(int, input().split()))

lr = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    li, ri = list(map(int, input().split()))
    lr[li][ri] += 1
    
for i in range(n+1):
    for j in range(n):
        lr[i][j+1] += lr[i][j]
for i in range(n+1):
    for j in range(n):
        lr[j+1][i] += lr[j][i]

for _ in range(qn):
    pi, qi = list(map(int, input().split()))
    ans = lr[qi][qi] - lr[qi][pi-1] - lr[pi-1][qi] +lr[pi-1][pi-1]
    
    print(ans)
### BUGGY CODE ###

H,W,D = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for _ in range(H)]
Q = int(input())

tmp = [0]*(H*W)
for i in range(H):
    for j in range(W):
        tmp[A[i][j]-1] = [i,j]

ans = []
for _ in range(Q):
    aaa = 0
    L,R = [int(zz) for zz in input().split()]
    bl = tmp[L-1][0]
    br = tmp[L-1][1]
    for i in range(L+D,R+1,D):
        l = tmp[i-1][0]
        r = tmp[i-1][1]
        aaa += abs(bl-l) + abs(br-r)
        bl = l
        br = r
    ans.append(aaa)

[print(i) for i in ans]


### FIXED CODE ###

H,W,D = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for _ in range(H)]
Q = int(input())

tmp = [0]*(H*W)
for i in range(H):
    for j in range(W):
        tmp[A[i][j]-1] = [i,j]

ans = [0]*(H*W)
for i in range(D):
    bl = tmp[i][0]
    br = tmp[i][1]
    i += D
    zp = 0
    while i < H*W:
        l = tmp[i][0]
        r = tmp[i][1]
        ans[i] = abs(bl-l)+abs(br-r)+zp
        zp = ans[i]
        bl = l
        br = r
        i += D

jjj = []
for _ in range(Q):
    L,R = [int(i) for i in input().split()]
    jjj.append(ans[R-1]-ans[L-1])

[print(i) for i in jjj]
### BUGGY CODE ###

from collections import deque
infty = 10 ** 4

def BFS(G, D, u):
    queue = deque()
    queue.append(u)
    visit = [False for k in range(len(D))]
    d = 0
    L = 1
    visit[i] = True
    while queue:
        add_v = 0
        while L > 0:
            v = queue.popleft()
            D[v] = d
            L -= 1
            for j in G[v]:
                if not visit[j]:
                    queue.append(j)
                    visit[j] = True
                    add_v += 1
        d += 1
        L = add_v
    return D

N, X, Y = map(int, input().split())
G = [[1]]
for i in range(1, N - 1):
    G.append([i - 1, i + 1])
G.append([N - 2])
G[X - 1].append(Y - 1)
G[Y - 1].append(X - 1)
dist = [[infty for j in range(N)] for i in range(N)]
for i in range(N):
    dist[i] = BFS(G, dist[i], i)
count = [0 for i in range(N)]
for i in range(N):
    for j in range(N):
        count[dist[i][j]] += 1
for i in range(N - 1):
    print(count[i + 1] // 2)

### FIXED CODE ###

N, X, Y = map(int, input().split())
count = [0 for i in range(N)]
dist = [[-1 for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        dist[i][j] = min(abs(j - i), abs(X - 1 - i) + 1 + abs(Y - 1 - j))
for i in range(N):
    for j in range(i + 1, N):
        count[dist[i][j]] += 1
for i in range(1, N):
    print(count[i])
### BUGGY CODE ###

N, B, R = map(int, input().split())

Line = ''

Appended_line = ''
for i in range(B):
  Appended_line += 'b'
for i in range(R):
  Appended_line += 'r'

while(N > len(Line)):
  Line += Appended_line

ans = Line[:N].count('b')

print(ans)

### FIXED CODE ###

N, B, R = map(int, input().split())

ans = (N // (B+R)) * B
rest = N % (B+R)

if rest <= B:
  print(ans+rest)
else:
  print(ans+B)
### BUGGY CODE ###

from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[j + (w * i)] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[j + (w * i)] = dist[y + (w * x)] + 1
                que.append((i, j)), frag.add((i, j))
    return max(dist)


h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(bfs(a))


### FIXED CODE ###

from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[i][j] < 0:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j))
    return dist[x][y]


h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(bfs(a))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    cnt = 0
    for i in range(N):
        for j in range(N):
            if i != j and A[i] % A[j] == 0:
                break
        else:
            cnt += 1
    
    print(cnt)

    return


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter


def solve(N: int, A: "List[int]"):
    countA = Counter(A)
    A.sort()
    l = [True for _ in range(A[-1] + 1)]
    for i in range(N):
        j = 2
        while A[i] * j <= A[-1]:
            l[A[i] * j] = False
            j += 1
    cnt = 0
    for a in A:
        cnt += (l[a] and countA[a] == 1)
    print(cnt)




# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

import math
import sys
import itertools
from math import gcd
from math import sqrt
from sys import stdin
def input() : return stdin.readline().rstrip()
def mips():
    return map(int,input().split())
def ii():
    return int(input())
sys.setrecursionlimit(10**9)

N,M,K = mips()
A = [i for i in mips()]
B = [i for i in mips()]
# N,M <= 200000
ans = 0
clock = K
A2 = [0]
B2 = [0]
for i in range(1,N+1):
    ai = A2[i-1] + A[i-1]
    A2.append(ai)
for i in range(1,M+1):
    bi = B2[i-1] + B[i-1]
    B2.append(bi)
for i in range(N+1):
    j = M
    if A2[i] > K:
        break
    while (j >= 0):
        if A2[i] + B2[j] <= K:
            ans = max(ans,i+j)
        j -= 1
print(ans)

### FIXED CODE ###

import math
import sys
import itertools
from math import gcd
from math import sqrt
from sys import stdin
def input() : return stdin.readline().rstrip()
def mips():
    return map(int,input().split())
def ii():
    return int(input())
sys.setrecursionlimit(10**9)

N,M,K = mips()
A = [i for i in mips()]
B = [i for i in mips()]
# N,M <= 200000
ans = 0
clock = K
A2 = [0]
B2 = [0]
for i in range(1,N+1):
    ai = A2[i-1] + A[i-1]
    A2.append(ai)
for i in range(1,M+1):
    bi = B2[i-1] + B[i-1]
    B2.append(bi)
j = M
for i in range(N+1):
    if A2[i] > K:
        break
    while (B2[j] + A2[i] > K):
        j -= 1
    ans = max(ans,i+j)
print(ans)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())

res=0
tmp=n
tmp1=0

for i in range(n//r+1):
	tmp = tmp - i*r
	tmp1 = tmp
	for j in range(n//g+1):
		tmp1 = tmp - j*g
		if tmp1 >= 0 and tmp1%b==0:
			res = res + 1
			#print(i, j, int(tmp1/t2[2]))
		tmp1 = tmp
	tmp=n

print(res)

### FIXED CODE ###

r,g,b,n = map(int,input().split())

res=0
tmp=n
tmp1=0
re=n//r+1
ge=n//g+1

for i in range(re):
	tmp = tmp - i*r
	tmp1 = tmp
	for j in range(ge):
		tmp1 = tmp - j*g
		if tmp1 >= 0 and tmp1%b==0:
			res = res + 1
			#print(i, j, int(tmp1/t2[2]))
		tmp1 = tmp
	tmp=n

print(res)
### BUGGY CODE ###

import itertools
n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(q)] 
u=[]
for i in range(1,m+1):
  for k in range(n):
    u.append(i)
a=list(set(list(itertools.combinations(u,n))))
ans=[]

for i in range(len(a)):
  c=0
  for k in range(len(l)):
    if a[i][l[k][1]-1]-a[i][l[k][0]-1]==l[k][2]:
      c+=l[k][3]
  ans.append(c)
print(max(ans))


### FIXED CODE ###

import sys
from collections import Counter
from collections import deque
import math
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

from itertools import combinations_with_replacement as cwr
n,m,q=mp()
l=[lmp() for i in range(q)]
ans=0


for i in cwr(range(1,m+1),n):
    s=0
    for a,b,c,d in l:
        if i[b-1]-i[a-1]==c:
            s+=d
    ans=max(ans,s)
print(ans)
### BUGGY CODE ###

def e(a,b,c):
    if b==0:
        return 1
    aa=1
    if b%2==1:
        aa=a
    return (aa*(e(a,b//2,c)**2))%mod
n=int(input())
pre=[1]
mod=998244353
for i in range(n//2+100):
    pre.append((pre[-1]*2)%mod)
p=[1]
for i in range(n):
    p.append((p[-1]*(i+1))%mod)
tot=1
for i in range(n):
    tot*=3
    tot%=mod
#print(1)
#print(tot)
for i in range(n//2+1,n+1):
    c=(p[n]*e(p[i],mod-2,mod)*e(p[n-i],mod-2,mod)*pre[n-i])%mod
    c%=mod
    tot-=c
    tot-=c
    tot%=mod
print(tot)

### FIXED CODE ###


n=int(input())
pre=[1]*(n//2+200)
pp=[1]*(n+1)
mod=998244353
for i in range(1,n//2+100):
    pre[i]=((pre[i-1]*2)%mod)
    
p=[1]*(n+1)
for i in range(n):
    p[i+1]=((p[i]*(i+1))%mod)
pp[-1] = pow(p[-1], mod - 2, mod)
 
for i in range(2, n + 1):
	pp[-i] = int((pp[-i + 1] * (n + 2 - i)) % mod)
tot=1
for i in range(n):
    tot*=3
    tot%=mod
#print(1)
#print(tot)
cc=0
for i in range(n//2+1,n+1):
    c=(((((p[n]*pp[i])%mod)*pp[n-i])%mod)*pre[n-i])%mod
    c%=mod
    cc+=c
tot-=cc
tot-=cc
tot%=mod
print(tot)
### BUGGY CODE ###

n = int(input())
num_list = []

for _ in range(n):
    cmd = (input().split())
    if   cmd[0] == 'insert':
        num_list.insert(0,int(cmd[1]))
    elif cmd[0] == 'delete':
        if int(cmd[1]) in num_list:
            idx = num_list.index(int(cmd[1]))
            del(num_list[idx])
    elif cmd[0] == 'deleteFirst':
        del(num_list[0])
    elif cmd[0] == 'deleteLast':
        num_list.pop()

ans_list = [str(i) for i in num_list]
print(' '.join(ans_list))


### FIXED CODE ###

from collections import deque
dq = deque()
for _ in [None]*int(input()):
    s = input()
    if s == "deleteFirst":
        dq.popleft()
    elif s == "deleteLast":
        dq.pop()
    else:
        a, b = s.split()
        if a == "insert":
            dq.appendleft(b)
        else:
            if b in dq:
                dq.remove(b)
print(" ".join(dq))
### BUGGY CODE ###

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

t = 0
for i in range(n-k+1):
    t_2 = 0
    if i == 0:
        for j in range(k):
            t += a[j+i]
        continue
    for j in range(k):
        t_2 += a[j+i]
    if t_2>t:
        print("Yes")
    else:
        print("No")
    t = t_2


### FIXED CODE ###

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

for i in range(n-k):
    if a[i+k] > a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N, K = map(int, input().split())
p = [int(x) for x in input().split()]
ans = 0
f = N-K+1
for i in range(f):
    s = sum(p[i : i + K])
    if ans < s:
        ans = s
print((ans + K) / 2)

### FIXED CODE ###

N, K = map(int, input().split())
p = [int(x) for x in input().split()]
s = sum(p[0 : K])
ans = sum(p[0 : K])
f = N-K+1
for i in range(1, f):
    s = s - p[i-1] + p[i + K - 1]
    if ans <= s:
        ans = s
print((ans + K) / 2)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
lr = [list(map(lambda x: int(x)-1, input().split())) for _ in range(q)]
for x in lr:
    tmp = s[x[0]:x[1]+1]
    print(tmp.count('AC'))

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
lr = [list(map(lambda x: int(x)-1, input().split())) for _ in range(q)]

ac = [0]*n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        ac[i+1]= ac[i]+1
    else:
        ac[i+1] = ac[i]
for x in lr:
    print(ac[x[1]] - ac[x[0]])
### BUGGY CODE ###

N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))

i = 1
pas = [i]
k = 1
while k <= K:
    if A[i] in pas:
        rps = pas.index(A[i]) # roop start index
        ans = A[i]
        break
    pas.append(A[i])
    ans = A[i]
    i = A[i]
    k += 1
    
if k >= K:
    print(ans)
else:
    rpnum = (K-rps)%(len(pas)-rps) # roop number
    print(pas[rps+rpnum])

### FIXED CODE ###

import numpy as np

def main():
    N,K = map(int,input().split())
    A = [0]
    A += list(map(int,input().split()))
    A = np.array(A)
    
    i = 1
    pas = np.zeros(N)
    pas[0] = i
    k = 1
    pass_set = set(pas)
    while k <= K:
        if A[i] in pass_set:
            rps = np.where(pas==(A[i]))[0]
            ans = A[i]
            break
        pas[k] = A[i]
        pass_set.add(A[i])
        ans = A[i]
        i = A[i]
        k += 1

    if k >= K:
        print(ans)
    else:
        rpnum = (K-rps[0])%(k-rps)
        print(int(pas[rps[0]+rpnum]))

main()
### BUGGY CODE ###

N, M = map(int,input().split())
A = [0] * (N+1)
for i in range(M):
    L,R = map(int,input().split())
    for i in range(L,R+1):
        A[i] += 1
print(sum([1 for a in A if a == M]))

### FIXED CODE ###

N, M = map(int,input().split())
Ls,Rs = [],[]
for i in range(M):
    L,R = map(int,input().split())
    Ls.append(L)
    Rs.append(R)

print(max(0,min(Rs)-max(Ls)+1))
### BUGGY CODE ###

from bisect import bisect_right

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

cnt = [0] * N
for i in range(N):
    cnt[i] = N - bisect_right(C, B[i])
    
res = 0
for i in range(N):
    idx = bisect_right(B, A[i])
    if idx < N:
        res += sum(cnt[idx:])
print(res)


### FIXED CODE ###

from bisect import bisect_left, bisect_right
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()
print(sum(bisect_left(A, i) * (N - bisect_right(C, i)) for i in B))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

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

graph = [{} for _ in range(N)]
for l, r, d in LRD:
	l, r = l - 1, r - 1
	graph[l][r] = d
	graph[r][l] = -d

visited = [False] * N
def dfs(v, p, d, depths):
	if visited[v]:
		return True
	visited[v] = True

	if depths[v] != -1:
		return True
	depths[v] = d

	for n in graph[v]:
		if n == p:
			continue
		n_depth = d + graph[v][n]
		if depths[n] != -1 and depths[n] != n_depth:
			return False
		result = dfs(n, v, n_depth, depths)
		if not result:
			return False
	return True

for n in range(N):
	if not dfs(n, -1, 0, [-1] * N):
		print("No")
		break
else:
	print("Yes")


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

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

graph = [{} for _ in range(N)]
for l, r, d in LRD:
	l, r = l - 1, r - 1
	graph[l][r] = d
	graph[r][l] = -d

visited = [False] * N
depths = [-1] * N
def dfs(v, p, d):
	if visited[v]:
		return True
	visited[v] = True
	depths[v] = d

	for n in graph[v]:
		if n == p:
			continue
		n_depth = d + graph[v][n]
		if depths[n] != -1 and depths[n] != n_depth:
			return False
		result = dfs(n, v, n_depth)
		if not result:
			return False
	return True

for n in range(N):
	if not dfs(n, -1, 0):
		print("No")
		break
else:
	print("Yes")
### BUGGY CODE ###

s = input()
MOD = 2019

dp = [[0] * (MOD) for i in range(len(s) + 1)]

dp[0][0] = 0
for i in range(len(s)):
    tmp = int(s[i])
    for val in range(MOD):
        dp[i + 1][((val * 10) + tmp) % MOD] += dp[i][val]
    dp[i + 1][tmp] += 1

ans = 0
for i in range(len(s) + 1):
    ans += dp[i][0]
    
print(ans)


### FIXED CODE ###

s = input()
MOD = 2019

dp = [0] * MOD
dq = [0] * MOD
ans = 0

for i in range(len(s)):
    tmp = int(s[i])
    if i % 2 == 0:
        for val in range(MOD):
            dp[((val * 10) + tmp) % MOD] += dq[val]
            dq[val] = 0
        dp[tmp] += 1
        ans += dp[0]

    else:
        for val in range(MOD):
            dq[((val * 10) + tmp) % MOD] += dp[val]
            dp[val] = 0
        dq[tmp] += 1
        ans += dq[0] 
    
print(ans)
### BUGGY CODE ###

from math import factorial
import math
def cmb(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

def main():
    N, M = map(int, input().split())
    A = [-1] + [int(input()) for i in range(M)] + [N + 1]

    d = [0] * (len(A) - 1)
    for i in range(len(A) - 1):
        if A[i+1] - A[i] == 1:
            print(0)
            exit(0)
        d[i] = A[i+1] - 1 - (A[i] + 1)

    ans = 1
    for dd in d:
        if dd > 1:
            tmp = 0
            for j in range(dd//2 + 1):
                tmp += cmb(dd - j, j)
            ans *= tmp

    print(ans % 1000000007)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
def cmb(n, r, mod, g1, g2):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def main():
    N, M = map(int, input().split())
    A = [-1] + [int(input()) for i in range(M)] + [N + 1]

    mod = 10**9+7 #出力の制限
    N = 10**5
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )

    d = [0] * (len(A) - 1)
    for i in range(len(A) - 1):
        if A[i+1] - A[i] == 1:
            print(0)
            exit(0)
        d[i] = A[i+1] - 1 - (A[i] + 1)

    ans = 1
    for dd in d:
        if dd > 1:
            tmp = 0
            for j in range(dd//2 + 1):
                tmp += cmb(dd - j, j, mod, g1, g2)
            ans *= tmp

    print(ans % 1000000007)

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

N, M = map(int, input().split())
left = []
right = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    left.append(b)
  elif b == N:
    right.append(a)
    
flag = False
for r in right:
  if r in left:
    flag = True
    break
    
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')


### FIXED CODE ###

N, M = map(int, input().split())
left = []
right = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    left.append(b)
  elif b == N:
    right.append(a)
    
flag = False
left = set(left)
for r in right:
  if r in left:
    flag = True
    break
    
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')