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

#!/usr/bin/env python3
import sys
import numpy as np

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = np.zeros((N, 13))
    if S[N-1] != '?':
        dp[0, int(S[N-1])] = 1
    else:
        dp[0] = np.array([1,1,1,1,1,1,1,1,1,1,0,0,0])
    for i in range(1, len(S)):
        ii = N - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = (ll * 10 ** i) % 13
                    if j >= kk:
                        dp[i, j] += dp[i-1, j - kk]
                    if j < kk:
                        dp[i, j] += dp[i-1, 13 + j - kk]
                    dp[i, j] %= MOD
            else:
                x = int(S[ii])
                m = x * 10 ** i % 13
                k = j
                if j < m:
                    k = j + 13
                dp[i, j] = dp[i-1, k-m]
                dp[i, j] %= MOD
    print(int(dp[N-1, 5]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[N-1] != '?':
        dp[0][int(S[N-1])] = 1
    else:
        dp[0] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    ten = [1]
    for i in range(1, len(S)):
        ten.append(ten[-1] * 10 % 13)
        ii = len(S) - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = ll * ten[i] % 13
                    dp[i][j] += dp[i-1][(13 + j - kk)%13]
                    dp[i][j] %= MOD
            else:
                x = int(S[ii])
                m = x * ten[i] % 13
                dp[i][j] = dp[i-1][(13+j-m)%13]
                dp[i][j] %= MOD
    print(dp[len(S)-1][5])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

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

import sys
for line in sys.stdin:
    n=int(line)
    plist = [1 for i in xrange(n+1)]
    plist[0]=0
    plist[1]=0
    for x in xrange(int(n**0.5)+1):
        if plist[x] == 1:
            i=2
            while True:
                pos0 = x*i
                if pos0 < len(plist):
                    plist[pos0] = 0
                else:
                    break
                i+=1
    print plist.count(1)

### FIXED CODE ###

#! -*- coding:utf-8 -*-
import sys
# import time
for line in sys.stdin:
  n=int(line)
  # n=input()
  # start = time.time()
  #plist = [1 for i in xrange(n+1)]
  #??¨??¨1???????????????
  #1?????¨???????????????????´???°??¨??????
  plist = [1]*(n+1)
  #0??¨1????´???°?????????????????§0???????????????
  plist[0]=plist[1]=0
  i=2
  #??¶??°????????????????????????
  while True:
      pos0 = 2*i
      if pos0 < len(plist):
          plist[pos0] = 0
      else:
          break
      i+=1
  #???????????¨????????????????????????
  for x in xrange(3,int(n**0.5)+1):
    if plist[x]:
      for pos0 in xrange(x**2,n+1,x):
        plist[pos0] = 0
  # elapsed_time = time.time()-start
  # print elapsed_time
  print plist.count(1)
### BUGGY CODE ###

N = int(input())

P = list(map(int,input().split()))

result = 0
for i in range(N):
    flag = True
    for j in range(i,-1,-1):
        if P[i] > P[j]:
            flag = False
            break
    if flag:
        result += 1

print(result)

### FIXED CODE ###

N = int(input())

P = list(map(int,input().split()))

result = 0
current_min = 10**6
for i in range(N):
    current_min = min(current_min, P[i])
    if P[i] <= current_min:
        result += 1

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

S=raw_input()
L=len(S)

M=10**9+7

dp=[ [ 0 for i in range(4) ] for k in range(L+1) ]
all=1

for i in range(L):
	if S[i]=="A":
		dp[i+1][1]=dp[i][1]+all
		dp[i+1][2]=dp[i][2]
		dp[i+1][3]=dp[i][3]
	if S[i]=="B":
		dp[i+1][2]=dp[i][2]+dp[i][1]
		dp[i+1][3]=dp[i][3]
		dp[i+1][1]=dp[i][1]
	if S[i]=="C":
		dp[i+1][3]+=dp[i][3]+dp[i][2]
		dp[i+1][2]=dp[i][2]
		dp[i+1][1]=dp[i][1]

	if S[i]=="?":
		dp[i+1][1]=dp[i][1]*3+all
		dp[i+1][2]=dp[i][2]*3+dp[i][1]
		dp[i+1][3]=dp[i][3]*3+dp[i][2]
		all*=3

	dp[i+1][1]%=M
	dp[i+1][2]%=M
	dp[i+1][3]%=M
	all%M

print ( dp[-1][3] ) %M


### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

nums = []
nums = input().split()
N = int(nums[0])
Y = int(nums[1])
Right = 0
for c in range(N+1) :
    for b in range(N + 1):
        for a in range(N + 1):
            if( Y == 10000 * a + 5000 * b + 1000 *c ):
                if (N == (a + b + c)):
                    Right = 1
                    break
                else:
                    continue
        else:
            continue
        break
    else:
        continue
    break
if( Right == 0 ):
    print("-1 -1 -1")
else :
    print(a,b,c)

### FIXED CODE ###

nums = []
nums = input().split()
N = int(nums[0])
Y = int(nums[1])
Right = 0
for a in range(N+1) :
    for b in range(N + 1 - a):
        c = N - a - b
        if( Y == 10000 * a + 5000 * b + 1000 *c ):
            if (N == (a + b + c)):
                Right = 1
                break
            else:
                continue
    else:
        continue
    break
if( Right == 0 ):
    print("-1 -1 -1")
else :
    print(a,b,c)
### BUGGY CODE ###

class BIT:
    # 1-indexed
    def __init__(self, n):
        self.size = n + 1
        self.bit = [0] * self.size

    def add(self, i, x):
        """Add x to a[i]."""
        while i < self.size:
            self.bit[i] += x
            i += i & -i

    def sumup(self, i):
        """Sum a[1]~a[i]."""
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query(self, i, j):
        """Sum a[i]~a[j]."""
        return self.sumup(j) - self.sumup(i - 1)


N, Q = map(int, input().split())
C = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(Q)]

ans = [0] * Q
last_appeared = [0] * (N + 1)
bit = BIT(N + 1)
rm = 0
for i, (l, r) in sorted(enumerate(X), key=lambda x: x[1][1]):
    for j in range(rm + 1, r + 1):
        if last_appeared[C[j - 1]] > 0:
            bit.add(last_appeared[C[j - 1]], -1)
        last_appeared[C[j - 1]] = j
        bit.add(j, 1)

    rm = r
    ans[i] = bit.query(l, r)

print(*ans, sep="\n")


### FIXED CODE ###

class BIT:
    # 1-indexed
    def __init__(self, n):
        self.size = n + 1
        self.bit = [0] * self.size

    def add(self, i, x):
        """Add x to a[i]."""
        while i < self.size:
            self.bit[i] += x
            i += i & -i

    def sumup(self, i):
        """Sum a[1]~a[i]."""
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query(self, i, j):
        """Sum a[i]~a[j]."""
        return self.sumup(j) - self.sumup(i - 1)


N, Q = map(int, input().split())
C = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(Q)]

ans = [0] * Q
last_appeared = [0] * (N + 1)
bit = BIT(N + 1)
rm = 0
for i, (l, r) in sorted(enumerate(X), key=lambda x: x[1][1]):
    for j in range(rm + 1, r + 1):
        if last_appeared[C[j - 1]] > 0:
            bit.add(last_appeared[C[j - 1]], -1)
        last_appeared[C[j - 1]] = j
        bit.add(j, 1)

    rm = r
    ans[i] = bit.query(l, r)

print(*ans, sep="\n")
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L = sorted(L)

res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect_left(L[j+1:], L[i]+L[j])
        res += idx

print(res)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L.sort()
res = 0
for i in range(N):
    for j in range(i+1, N):
        idx = bisect_left(L, L[i]+L[j])
        res += max(0,idx-(j+1))
print(res)
### BUGGY CODE ###

s = list(input())
l = len(s)

W = 0

def f(n):
  for i in range(1, l-n+1):
    global W
    if W == 1: break
    slice = s[n-1:n+i]
    ls = len(slice)
#    print("切り出した文字列の長さlsは" + str(ls))
    y = list(set(slice))
    ly = len(y) #重複を消した後の文字数
#    print(y)
    for j in range(0, ly):
      sc = slice.count(y[j])
#      print(y[j] + "は" + str(sc) + "個") #文字の個数カウント
      if ls - sc >= sc: #その文字の個数が切り出した文字列の半分以下ならば
#        print(n)
#        print("lyは" + str(ly))
        if ly == 2 and n == l-1: 
          print(-1, -1)
          break
        pass
      else:
#        print("unbalance")
        print(n, n+i)
        W = 1
        break
      
for i in range(1, l):
  if W == 1: break
  f(i)

### FIXED CODE ###

from sys import exit

s = input()
l = len(s)

for i in range(l-2):
  if s[i] == s[i+1]:
    print(i+1, i+3)
    exit()
  if s[i] == s[i+2]:
    print(i+1, i+3)
    exit()

if s[l-2] == s[l-1]:
  print(l-1, l)
else:
  print(-1, -1)
### BUGGY CODE ###

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

res = 0
for i in range(N):
  for j in range(i):
    if P[i] <= P[j]:
      continue
    else:
      break
  else:
    res += 1
print(res)

### FIXED CODE ###

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

res = 1
minp = P[0]
for p in P[1:]:
  if p < minp:
    minp = p
    res += 1
print(res)
### BUGGY CODE ###

import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx < end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.999 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
start = 0
K = L * int(N ** 0.3 + 2 )
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import copy
x = int(input())

candidates = [0]

for i in range(1, x + 1):
    # print(candidates)
    for c in copy.deepcopy(candidates):
        candidates.append(c+i)
        candidates.append(c-i)

    if x in candidates:
        print(i)
        break


### FIXED CODE ###

import copy
x = int(input())

m = 0

for i in range(1, x + 1):
    m += i
    if x <= m:
        print(i)
        break
### BUGGY CODE ###

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

DP = [0] * (N+1)

for i in range(2, N+1):
  s = []
  for j in range(1, K+1):
    if i > j:
      dp = DP[i-j] + abs(H[i-j] - H[i])
      s.append(dp)
  DP[i] = min(s)
print(DP[N])


### FIXED CODE ###

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

DP = [0] * (N+1)

for i in range(2, N+1):
  k = max(i-K, 1)
  DP[i] = min(dp + abs(h - H[i]) for dp, h in zip(DP[k:i], H[k:i]))
print(DP[N])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
t = 0
L = []
for e in a:
    L.append(e%(10**9+7))


for i in range(len(a)):
    for j in range(i, len(a)):
        if i != j:
          t += L[i]*L[j]

print(t%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
t = 0
r = 0
mod = 10**9+7
for i in range(n-1, 0, -1):
    r += a[i]
    t += a[i-1]*r
print(t%mod)
### BUGGY CODE ###

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

for i in range(n):
    p = 0
    cnt = 0
    for j in a[:i] + a[i+1:]:
        cnt += abs(j-p)
        p = j
    
    cnt += abs(j-0)
    
    print(cnt)

### FIXED CODE ###

n = int(input())
a = [0] + list(map(int, input().split())) + [0]

cost = 0
for i in range(n+2):
    cost += (abs(a[i] - a[i-1]))

for i in range(1, n+1):
    print(cost + abs(a[i-1]-a[i+1]) - (abs(a[i-1]-a[i]) + abs(a[i]-a[i+1])))
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
p,q=0,1
for i in range(1,n+1):
    p,q=q,(p+q)%(10**9+7)*(not i in a)
print(q)


### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for _ in range(m)])
p,q=0,1
for i in range(1,n+1):
    p,q=q,(p+q)*(not i in a)
print(q%(10**9+7))
### BUGGY CODE ###

K=int(input())

i=1

while True:
	if 7*int("1"*i)%K==0:
		exit(print(i))
	i+=1

### FIXED CODE ###


K=int(input())
a_i=7%K
i=1
if a_i==0:
	exit(print(1))
while True:
	i+=1
	a_i=(10*a_i+7)%K
	if a_i==0:
		print(i)
		exit()
	if i>=K:
		print(-1)
		exit()
### BUGGY CODE ###

H, W = map(int, input().split())
ans = 0
blk = []
for h in range(H):
    line = input()
    for w in range(W):
        if line[w] == '#':
            blk.append([h+1, w+1])
cnt = len(blk)
for h in range(H):
    for w in range(W):
        tmp = H + W
        if line[w] == '.':
            for y, x in blk:
                tmp = min(abs(h+1 - y) + abs(w+1 - x), tmp)
            ans = max(tmp, ans)
print(ans)


### FIXED CODE ###

import numpy as np

H,W = map(int,input().split())
A = []
for i in range(H):
    A.append([0 if i == "#" else H+W for i in list(input())])
A = np.array(A)

for i in range(H-1):
  A[i+1, :] = np.minimum(A[i, :] + 1, A[i+1, :])
for i in range(H-1,0,-1):
  A[i-1,:] = np.minimum(A[i,:]+1,A[i-1,:])
for i in range(W-1):
  A[:,i+1] = np.minimum(A[:,i]+1,A[:,i+1])
for i in range(W-1,0,-1):
  A[:,i-1] = np.minimum(A[:,i]+1,A[:,i-1])
print(np.max(A))
### BUGGY CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,m,k = map(int,ipt().split())
    fl = [[] for i in range(n)]
    bl = [set() for i in range(n)]
    for i in range(m):
        a,b = map(int,ipt().split())
        fl[a-1].append(b-1)
        fl[b-1].append(a-1)
    for i in range(k):
        c,d = map(int,ipt().split())
        bl[c-1].add(d-1)
        bl[d-1].add(c-1)

    ans = [-1]*n
    al = [True]*n
    for i in range(n):
        if al[i]:
            q = [i]
            al[i] = False
            st = set([i])
            while q:
                qi = q.pop()
                for j in fl[qi]:
                    if al[j]:
                        st.add(j)
                        al[j] = False
                        q.append(j)
            for j in st:
                ans[j] = len([i for i in st if i not in bl[j]])-len(fl[j])-1

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


    return None

if __name__ == '__main__':
    main()


### FIXED CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,m,k = map(int,ipt().split())
    fl = [[] for i in range(n)]
    bl = [set() for i in range(n)]
    for i in range(m):
        a,b = map(int,ipt().split())
        fl[a-1].append(b-1)
        fl[b-1].append(a-1)
    for i in range(k):
        c,d = map(int,ipt().split())
        bl[c-1].add(d-1)
        bl[d-1].add(c-1)

    ans = [-1]*n
    al = [True]*n
    for i in range(n):
        if al[i]:
            q = [i]
            al[i] = False
            st = set([i])
            while q:
                qi = q.pop()
                for j in fl[qi]:
                    if al[j]:
                        st.add(j)
                        al[j] = False
                        q.append(j)
            lst = len(st)
            for j in st:
                tmp = lst-len(fl[j])-1
                for k in bl[j]:
                    if k in st:
                        tmp -= 1
                ans[j] = tmp

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


    return None

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

import math
A, B = map(int, input().split())
gcd = math.gcd(A, B)
ans = 1
if gcd%2==0:
  ans += 1
if gcd >= 3:
  pn = [2]
  for i in range(3, gcd+1, 2):
    check=True
    for num in pn:
      if i % num == 0:
        check=False
        break
    if check:
      pn.append(i)
      if A%i==0 and B%i==0:
        ans += 1
print(ans)

### FIXED CODE ###

import math
A, B = map(int, input().split())
gcd = math.gcd(A, B)
ans = [1]
while gcd % 2 == 0:
  ans.append(2)
  gcd = gcd // 2
f = 3
while f * f <= gcd:
  if gcd % f == 0:
    ans.append(f)
    gcd = gcd // f
  else:
    f += 2
if gcd != 1:
  ans.append(gcd)
print(len(set(ans)))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, a: "List[int]"):

    dp = [[0]*N for _ in range(N)]
    for sub in range(N):
        turn = sub % 2
        for i in range(N-sub):
            j = i+sub
            # i ~ jの数列に対して操作
            if i == j:
                if (N-sub+1) % 2 == 0:
                    dp[i][i] = a[i]
                else:
                    dp[i][i] = -a[i]
                continue

            if (N-sub+1) % 2 == 0:    # 先手番
                dp[i][j] = max(a[i] + dp[i+1][j], a[j]+dp[i][j-1])
            else:               # 後手番
                dp[i][j] = min(-a[i] + dp[i+1][j], -a[j]+dp[i][j-1])
    print(dp[0][N-1])
    return


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
INF = float("inf")


def solve(N: int, a: "List[int]"):

    dp = [[0]*N for _ in range(N)]
    for sub in range(N):
        turn = sub % 2
        for i in range(N-sub):
            j = i+sub
            # i ~ jの数列に対して操作
            if i == j:
                if (N-sub+1) % 2 == 0:
                    dp[i][i] = a[i]
                else:
                    dp[i][i] = -a[i]
                continue

            if (N-sub+1) % 2 == 0:    # 先手番
                dp[i][j] = max(a[i] + dp[i+1][j], a[j]+dp[i][j-1])
            else:               # 後手番
                dp[i][j] = min(-a[i] + dp[i+1][j], -a[j]+dp[i][j-1])
    print(dp[0][N-1])
    return


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 ###

x = int(input())
 
for val in range(x, x**1000000000) :
	if x ==2 :
		print(x)
		break
	elif ((2** val) % val) == 2 :
		print (val)
		break
	else :
		continue

### FIXED CODE ###

import math
x = int(input())
i = 0
flag = True
while flag:
  for k in range(2, int(math.sqrt(x+i)) + 1):
    if (x+i) % k == 0:
      i += 1
      break
  else:
      flag = False

print(x+i)
### BUGGY CODE ###

N = int(input())
S = list(str(input()))

min = 3*10**5
cont = 0


for i in range(1,N):
  cont = 0
  left = S[:i-1]
  right = S[i+1:]
  cont = left.count("W") + right.count("E")
  if min >= cont:
    min = cont

print(min)

### FIXED CODE ###

N = int(input())
S = list(str(input()))

min = 3*10**5
cnt = 0

cnt = S.count("E")
min = cnt

for i in S:
  if i == "E":
    cnt -= 1
  elif i == "W":
    cnt += 1
  if min >= cnt:
    min = cnt

print(min)
### BUGGY CODE ###

import itertools
N, M, R = map(int, raw_input().split())
r = [int(x)-1 for x in raw_input().split()]
D = []
for i in range(N):
  D.append([200000000]*N)
  D[i][i]=0
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
  a, b, C[i] = map(int, raw_input().split())
  A[i] = a-1
  B[i] = b-1
  D[A[i]][B[i]] = C[i]
  D[B[i]][A[i]] = C[i]
for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
ml = 2000000000
for p in itertools.permutations(r):
  l = 0
  for i in range(R-1):
    l += D[p[i]][p[i+1]]
  ml = min(ml, l)
print ml

### FIXED CODE ###

import itertools
N, M, R = map(int, raw_input().split())
r = [int(x)-1 for x in raw_input().split()]
D = []
for i in range(N):
  D.append([200000000]*N)
  D[i][i]=0
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
  a, b, C[i] = map(int, raw_input().split())
  A[i] = a-1
  B[i] = b-1
  D[A[i]][B[i]] = C[i]
  D[B[i]][A[i]] = C[i]
for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
ml = 2000000000
for p in itertools.permutations(r):
  l = 0
  for i in range(R-1):
    l += D[p[i]][p[i+1]]
  ml = min(ml, l)
print ml
### BUGGY CODE ###

N = int(input())
X = input()

d = {}
def popcount(s):
    if not s in d:
        d[s] = s.count('1')
    return d[s]

one = popcount(X)
K = int(X, 2)
for i in range(N):
    pop = one
    if X[i] == '1':
        pop -= 1
    else:
        pop += 1

    k = K
    bit = N-i-1
    if X[i] == '1':
        k -= 2**bit
    else:
        k += 2**bit
    ans = 0
    while k > 0:
        k %= pop
        pop = popcount(bin(k)[2:])
        ans += 1
    print(ans)


### FIXED CODE ###

N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)
### BUGGY CODE ###

n= input()
ans=0
for i in range(len(n)):
    for s in range(i+1,len(n)):
        if int(n[i:s+1])%2019 ==0:
            
            ans=ans+1
print(ans)



### FIXED CODE ###

s= input()[::-1]
mods= [0] * 2019
mods[0] = 1
num=0
d = 1
for c in s:
    num += int(c) * d
    num %= 2019
    d *= 10
    d %= 2019
    mods[num] += 1

ans = 0
for cnt in mods:
    ans += cnt * (cnt - 1) // 2

print(ans)