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

#encoding:utf-8

import numpy as np

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)

S_ = np.array(S)

def count_answer(x,y):
    count = 0
    actions = {0:[-1,0],1:[0,1],2:[1,0],3:[0,-1]}
    # print("x,y:",x,y)
    for action0 in range(4):
        next_x = x + actions[action0][0]
        next_y = y + actions[action0][1]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1:
            pass
        elif next_x >= H or next_y >= W:
            pass
        elif [next_x,next_y] in reach_position:
            pass
        elif S_[next_x,next_y] == ".":
            reach_position.append([next_x,next_y])
            for action in range(4):
                next_next_x = next_x +actions[action][0]
                next_next_y = next_y +actions[action][1]
                # print(next_next_x,next_next_y)
                if next_next_x == -1 or next_next_y == -1:
                    pass
                elif next_next_x >= H or next_next_y >= W:
                    pass
                elif S_[next_next_x,next_next_y] == "#":
                    tem_poss = count_answer(next_next_x,next_next_y)
                    for tem_pos in tem_poss:
                        if tem_pos in reach_position:
                            pass
                        else:
                            reach_position.append(tem_pos)
    # memory[[x,y]] = reach_position
    return reach_position

answer = 0
for i in range(H):
    for j in range(W):
        if S_[i,j] == "#":
            reach_position = []
            reach_position = count_answer(i,j)
            answer += len(reach_position)
print(answer)


### FIXED CODE ###

#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)


def count_answer(x,y,num_b,num_w):
    # print(used)

    if S[x][y] == "#":
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S[next_x][next_y] != S[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S[i][j] == "#":
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)
### BUGGY CODE ###

import collections
n,x,y = map(int,input().split())
h = [[] for _ in range(n+1) ]
for i in range(1,n+1):
    if i+1<n+1:
        h[i].append(i+1)
    if i-1>0:
        h[i].append(i-1)
h[x].append(y)
h[y].append(x)

k = [0]*n
for i in range(1,n+1):
    q = collections.deque([i])
    step = [-1]*(n+1)
    step[i] = 0
    while q:
        now = q.popleft()
        for hh in h[now]:
            if step[hh] == -1:
                q.append(hh)
                step[hh] = step[now]+1
                k[step[now]+1] += 1
for i in range(1,n):
    print(k[i]//2)

### FIXED CODE ###

import collections
n,x,y = map(int,input().split())
h = [[] for _ in range(n+1) ]
for i in range(1,n+1):
    if i+1<n+1:
        h[i].append(i+1)
    if i-1>0:
        h[i].append(i-1)
h[x].append(y)
h[y].append(x)

k = [0]*n
for i in range(1,n+1):
    q = collections.deque([i])
    step = [-1]*(n+1)
    step[i] = 0
    while q:
        now = q.popleft()
        for hh in h[now]:
            if step[hh] == -1:
                q.append(hh)
                step[hh] = step[now]+1
                k[step[now]+1] += 1
for i in range(1,n):
    print(k[i]//2)
### BUGGY CODE ###

def main():
    import sys
    from collections import deque
    
    input=sys.stdin.readline
    N,Q = map(int,input().split())
    AB = [[x for x in map(int,input().split())] for _ in range(N-1)]
    PX = [[x for x in map(int,input().split())] for _ in range(Q)]

    G = [[] for _ in range(N+1)]
    for a,b in AB:
        G[a].append(b)
        G[b].append(a)

    cnt = [0]*N
    for p,x in PX:
        cnt[p-1] += x

    color = ["WHITE"] * (N+1)
    stack = []
    stack = deque(stack)

    def dfs(u):
        stack.append(u)
        color[u] = "GRAY"

        while len(stack) > 0:
            u = stack[-1]
            if len(G[u]) == 0:
                color[u] = "BLACK"
                stack.pop()
            else:
                u_next = G[u].pop(0)
            if color[u_next] == "WHITE":
                color[u_next] = "GRAY"
                cnt[u_next-1] += cnt[u-1]
                stack.append(u_next)
    dfs(1)
    print(*cnt)


    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

N=int(input())
P=[int(i) for i in input().split()]

num = 0
#print(min(P[:1]))
for k in range(0,N):
	if min(P[:k+1]) == P[k]:
		num+=1
print(num)

### FIXED CODE ###

num = int(input())
A = list(map(int, input().split()))

a_min = 200001
count = 0
for a in A:
    if a < a_min:
        count += 1
        a_min = a

print(count)
### BUGGY CODE ###

import sys

sys.stdin.readline()
a = list(map(int, sys.stdin.readline().split()))

def largest_odd_idx(A):
    idx = -1
    max_a = 0
    for i, v in enumerate(A):
        if v % 2 == 0 and max_a < v:
            max_a = v
            idx = i
    return idx

cnt = 0
while True:
    idx = largest_odd_idx(a)
    if idx < 0:
        break
    for i in range(0, len(a)):
        if idx == i:
            a[i] //= 2
        else:
            a[i] *= 3
    cnt += 1
print(cnt)

### FIXED CODE ###

import math
import sys

sys.stdin.readline()
a = list(map(int, sys.stdin.readline().split()))

a = [x for x in a if x % 2 == 0]

cnt = 0
for x in a:
    while x % 2 == 0:
        x //= 2
        cnt += 1

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

n, k =map(int,input().split())
s = input()

sp = "1"
count = 0
cu = []
cd = []
for i in range(n):
    if sp == s[i]:
        count += 1
    else:
        if sp == "1":
            cu.append(count)
        else:
            cd.append(count)
        count = 1
    sp = s[i]
if sp == "1":
    cu.append(count)
else:
    cd.append(count)
ans = 0
for i in range(len(cd)):
    sn = 0
    ld = i
    rd = min(i + k - 1, len(cd)-1)
    sn += sum(cd[ld:rd+1])
    lu = i
    ru = min(rd+1,len(cu)-1)
    sn += sum(cu[lu:ru+1])
    ans = max(ans,sn)
if len(cd)==0:
    ans = n
print(ans)

### FIXED CODE ###

n, k =map(int,input().split())
s = input()

sp = "1"
count = 0
cu = []
cd = []
for i in range(n):
    if sp == s[i]:
        count += 1
    else:
        if sp == "1":
            cu.append(count)
        else:
            cd.append(count)
        count = 1
    sp = s[i]
if sp == "1":
    cu.append(count)
else:
    cd.append(count)
ans = 0
for i in range(len(cd)):
    ld = i
    rd = min(i + k - 1, len(cd)-1)
    lu = i
    ru = min(rd+1,len(cu)-1)        
    if i == 0:
        sn = 0
        sn += sum(cd[ld:rd+1])
        sn += sum(cu[lu:ru+1])
    else:
        if ldp < ld:
            sn-=cd[ldp]
        if rdp < rd:
            sn+=cd[rd]
        if lup < lu:
            sn-=cu[lup]
        if rup < ru:
            sn+=cu[ru]
    ans = max(ans,sn)
    ldp,rdp,lup,rup = ld,rd,lu,ru
if len(cd)==0:
    ans = n
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
mod = 10**9+7
numofA = 0
numofAB = 0
numofABC = 0
numofquestion = 1
for i in range(N):
    if S[i] == "?":
        numofABC = (numofABC*3+numofAB) % mod
        numofAB = (numofAB*3+numofA) % mod
        numofA = (numofquestion + numofA*3) % mod
        numofquestion *= 3
    elif S[i] == "C":
        numofABC = (numofAB+numofABC) % mod
    elif S[i] == "B":
        numofAB = (numofAB + numofA) % mod
    else:
        numofA = (numofquestion + numofA) % mod
print(numofABC)


### FIXED CODE ###

S = input()
N = len(S)
mod = 10**9+7
numofA = 0
numofAB = 0
numofABC = 0
numofquestion = 1
for i in range(N):
    if S[i] == "?":
        numofABC = (numofABC*3+numofAB) % mod
        numofAB = (numofAB*3+numofA) % mod
        numofA = (numofquestion + numofA*3) % mod
        numofquestion = (numofquestion * 3) % mod
    elif S[i] == "C":
        numofABC = (numofAB+numofABC) % mod
    elif S[i] == "B":
        numofAB = (numofAB + numofA) % mod
    else:
        numofA = (numofquestion + numofA) % mod
print(numofABC)
### BUGGY CODE ###

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

a = 0
sum_A = {}

for g in range(N):
	a += A[g]
	amari = a%M
	if amari in sum_A.keys():
		sum_A[amari] += 1
	else:
		sum_A[amari] = 1

if sum_A.get(0)!=None:
	ans = sum_A[0]
else:
	ans = 0

for l in range(len(sum_A)):
	if sum_A[list(sum_A)[l]] >= 2:
		ans += (sum_A[list(sum_A)[l]]-1)*sum_A[list(sum_A)[l]]/2
print(int(ans))

### FIXED CODE ###

from collections import defaultdict
from itertools import accumulate

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

acc=list(accumulate(A))

d=defaultdict(int)

ans=0
for i in range(N):
    if acc[i]%M==0:
        d[acc[i]%M]+=1
        ans+=d[acc[i]%M]
    else:
        d[acc[i]%M]+=1
        ans+=d[acc[i]%M]-1
print(ans)
### BUGGY CODE ###

from collections import defaultdict, deque


def solve():
    N, K = map(int, input().split())
    d = defaultdict(list)
    MOD = 10**9+7

    for _ in range(N-1):
        a, b = map(int, input().split())
        d[a].append(b)
        d[b].append(a)

    ans = K
    used = [0]*(N+1)
    used[1] = True
    q = deque([1])

    while q:
        a = q.popleft()
        s = 1 if a==1 else 2
        for b in d[a]:
            if used[b]:continue
            used[b] = True
            ans *= (K-s)
            s += 1
            q.append(b)

    ans %= MOD
    print(ans)

solve()

### FIXED CODE ###

from collections import defaultdict
v = defaultdict(list)
mod = 10**9+7

N, K = map(int, input().split())
for _ in range(N-1):
    a, b = map(int, input().split())
    v[a].append(b)
    v[b].append(a)

visited = [False]*(N+1)
ans = 1

q = [(1, 0, 0)]
while q:
    pos, parent, score = q.pop()
    visited[pos] = True
    ans *= (K-score)
    ans %= mod 
   
    a = 1 if pos==1 else 2
    b = 0

    for i in v[pos]:
        if visited[i]:continue
        q.append((i, pos, a+b))
        b += 1

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

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

ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        check = N - (R*r + G*g)
        if check >= 0 and check%B == 0:
            ans += 1
        # if check == 0:
        #     # print(r, g, check//B, check)
        #     ans += 1
        # elif check > 0 and check%B == 0:
        #         # print(r, g, check//B, check)
        #         ans += 1

print(ans)

### FIXED CODE ###

R,G,B,N = list(map(int, input().split()))
ans=0
for r in range(N//R+1):
    x = N-R*r
    for g in range(x//G+1):
        if (x-G*g)%B==0:
            ans+=1
print(ans)
### BUGGY CODE ###

import heapq
S = input()
cum = [0 for _ in range(len(S))]
dict = {}
length = len(S)
n = 0
for i in range(1,length+1):
    n = n + int(S[-i]) * 10**(i-1)
    cum[i-1] = n % 2019
    dict[cum[i-1]] = 0


for c in cum:
    dict[c] += 1
ans = 0
for k, v in dict.items():
    if k == 0:
        ans += v
    ans += v * (v-1) // 2

print(ans)

### FIXED CODE ###

import sys
import math
from collections import deque
from collections import Counter

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    S = SI()
    l = len(S)
    T = [0] * (l+1)
    inv_S = S[::-1]
    for i, s in enumerate(inv_S):
        s = int(s)
        T[i+1] = (T[i] + s * pow(10, i, 2019)) % 2019
    C = Counter(Counter(T).values())
    ans = 0
    for n, x in C.items():
        if n == 1: continue
        ans += cmb(n, 2) * x
    print(ans)


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

S = input()
mod = 10**9+7

N = len(S)
A1,A2,C1,C2 = [1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i] in ("B","?"):
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (3**A2[i])*A1[i] + 3**(A2[i]-1)*A2[i]
            if ta>mod:
                ta %= mod
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (3**C2[i])*C1[i] + 3**(C2[i]-1)*C2[i]
            if tc > mod:
                tc %= mod
        Ans += ta*tc
        if Ans > mod:
            Ans %= mod

print(Ans)

### FIXED CODE ###

S = input()
mod = 10**9+7

N = len(S)
A1,A2,C1,C2 = [1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i] in ("B","?"):
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = pow(3,A2[i],mod)*A1[i] + pow(3,A2[i]-1,mod)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = pow(3,C2[i],mod)*C1[i] + pow(3,C2[i]-1,mod)*C2[i]
        Ans += ta*tc
        Ans %= mod

print(Ans)
### BUGGY CODE ###

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

loc = 1
loclog=[1]
flag = 0

for i in range(1,K+1):
    loc = A[loc-1]
    if loc in loclog:
        roopstart = loclog.index(loc)
        roopend = len(loclog)
        flag = 1
        break
    loclog.append(loc)

if flag == 0:
    ans = loc
else:
    roopidx = (K+1-roopstart)%(roopend-roopstart)
    if roopidx == 0:
        ans = loclog[roopend-1]
    else:
        ans = loclog[roopstart+roopidx-1]
print(ans)

### FIXED CODE ###

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

loc = 1
loclog=[1]
flag = 0
hist = [0]*N

for i in range(K):
    hist[loc-1] = 1
    loc = A[loc-1]
    if hist[loc-1] != 0:
        roopstart = loclog.index(loc)
        roopend = len(loclog)
        flag = 1
        break
    loclog.append(loc)

if flag == 0:
    ans = loc
else:
    roopidx = (K+1-roopstart)%(roopend-roopstart)
    if roopidx == 0:
        ans = loclog[roopend-1]
    else:
        ans = loclog[roopstart+roopidx-1]
print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline


def main():
    n = int(readline().rstrip())
    aList = list(map(int, readline().rstrip().split()))
    for i in range(n):
        print(aList.count(i + 1))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    n = int(readline().rstrip())
    aList = sorted(list(map(int, readline().rstrip().split())))
    z = [0] * n
    for a in aList:
        z[a-1] += 1

    for i in range(n):
        print(z[i])


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

a, op, b = input().split()
while True:
  if op == '+' : print(a + b)
  elif op == '-' : print(a - b)
  elif op == '/' : print(a / b)
  elif op == '*' : print(a * b)
  else : break

### FIXED CODE ###

while True:
  a, op, b = input().split()
  a = int(a)
  b = int(b)
  if op == '+': print(a + b)
  elif op == '-': print(a - b)
  elif op == '/': print(a // b)
  elif op == '*': print(a * b)
  else: break
### BUGGY CODE ###

n,y=[int(x) for x in input().split()]
for i in range(y//10000,-1,-1):
    for j in range((y-10000*i)//5000,-1,-1):
        for k in range((y-10000*i-5000*j)//1000,-1,-1):
            if i+j+k==n and i*10000+j*5000+k*1000==y:
                print(i,j,k)
                exit()
print("-1 -1 -1")


### FIXED CODE ###

n,y=[int(x) for x in input().split()]
for i in range(y//10000,-1,-1):
    for j in range((y-10000*i)//5000,-1,-1):
        if (n-i-j)*1000==(y-i*10000-j*5000):
            print(i,j,n-i-j)
            exit()
print("-1 -1 -1")
### BUGGY CODE ###

import math

n = int(input())
s = int(input())
f = None
for i in range(2, math.ceil(math.sqrt(n))):
    c = 0
    k = n
    while k > 0:
        c += k % i
        k //= i
    if c == s:
        f = i
        break
if f is None:
    for i in range(int(math.sqrt(n)), 0, -1):
        b = n // i
        k = n
        c = 0
        while k > 0:
            c += k % b
            k //= b
        if s >= c and (s - c) % i == 0 and b - (s - c) // i > n // (i + 1):
            f = b - (s - c) // i
            break
if f is None and s == n: f = n + 1
if f is None: print(-1)
else: print(f)


### FIXED CODE ###

import math

n = int(input())
s = int(input())
f = None
for i in range(2, math.ceil(math.sqrt(n))):
    c = 0
    k = n
    while k > 0:
        c += k % i
        k //= i
    if c == s:
        f = i
        break
if f is None:
    for i in range(int(math.sqrt(n)), 1, -1):
        b = n // i
        k = n
        c = 0
        while k > 0:
            c += k % b
            k //= b
        if s >= c and (s - c) % i == 0 and b - (s - c) // i > n // (i + 1):
            f = b - (s - c) // i
            break
if f is None:
    if s == n: f = n + 1
    elif s <= (n + 1) // 2: f = n - s + 1
    elif s == 1: f = n
if f is None: print(-1)
else: print(f)
### BUGGY CODE ###

a = int(input())
i = 1
q = 1
for a in range(a):
 i = i*q
 q = q+1
 w = i%(10**9+7)
print(w)

### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):ans=(ans*i)%(10**9 + 7)
print(ans)
### BUGGY CODE ###

from fractions import gcd
A,B=map(int,input().split())
gcd_list=[]
so_list=[]
for num in range(1,gcd(A,B)+1):
    if A%num==0 and B%num==0:
        gcd_list.append(num)
num=len(gcd_list)
if num>4:
    gcd_list=gcd_list[:num//2]
for i in gcd_list:
    flag=0
    if len(so_list)==0:
        so_list.append(i)
    else:
        for num in so_list:
            if num==1:
                continue
            if i%num==0:
                flag=1
                break
        if flag==0:
            so_list.append(i)
print(len(so_list))


### FIXED CODE ###

from math import gcd
A, B = map(int,input().split())
max_cmn_div = gcd(A, B)

# 約数列挙関数
def make_divisor(n):
    divisor = []
    for i in range(1, int(n**(1/2))+1):
        if n % i == 0:
            divisor.append(i)
            if i != n//i:
                divisor.append(n//i)
    return divisor

def check_prime(n):
    for i in range(2, int(n**(1/2))+1):
        if n % i == 0:
            return 0
    return 1

cmn_div = make_divisor(max_cmn_div)
ans = 0
for i in cmn_div:
    if check_prime(i):
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
x = [0]*max(a)
for i in a:
    x[i-1]+=1

for i in range(1,n+1):
    x[a[i-1]-1]-=1
    count = 0
    for j in x:
        if j>=2:
            count += int((j*(j-1)/2))
    x[a[i-1]-1]+=1
    print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
x = [0]*max(a)
for i in a:
    x[i-1]+=1
# print(x)
count = 0
# x_ = [(k*(k-1))/2 for k in x if k>=2]
# count = sum(x_)
for j in x:
    if j>=2:
        count += int((j*(j-1)/2))
for i in range(n):
    if x[a[i]-1]>=2:
        print(count-x[a[i]-1]+1)
    else:
        print(count)
### BUGGY CODE ###

import sys
# 整数の入力
N,M=list(map(int, input().split()))
p=[]
q=0
count=[]
for i in range(0,M):
  p.append(list(map(int, input().split())))
  count.append(0)
for i in range(0,M):
  q+=p[i][0]-p[i][1]
if q%2==1:
  print("NO")
else:
  for j in range(0,M):
    for i in range(0,M):
      if p[i][0]==j or p[i][1]==j:
        count[j]+=1
  for j in range(0,M):
    if count[j]%2==1:
      print("NO")
      sys.exit()
  print("YES")

### FIXED CODE ###

import sys
# 整数の入力
N,M=list(map(int, input().split()))
p=[]
for i in range(0,N):
  p.append(0)
for i in range(0,M):
  count=list(map(int, input().split()))
  p[count[0]-1]+=1
  p[count[1]-1]+=1
for i in range(0,M):
  if p[i]%2==1:
    print("NO")
    sys.exit()
print("YES")
### BUGGY CODE ###

S = input()[::-1]
N = len(S)

"""
    例： S = '31415926535'
        S[3:8] = '15926535' が 2019 で割り切れるかどうか？
     <=> S[3:-1] - S[8:-1] が 2019 で割り切れるかどうか
     <=> S[3:-1] % 2019 == S[8:-1] % 2019 か
    よって、2019で割ったときの異なるあまりをそれぞれカウントすればよい
"""

mod_cnts = [0] * 2019
mod_cnts[0] = 1 # 累積和のはじめ
current_cusum, ans = 0, 0
for i in range(N):
    s = S[i]
    current_cusum += pow(10, i) * int(s) # 累積和
    current_cusum %= 2019
    mod_cnts[current_cusum] += 1

for cnt in mod_cnts:
    ans += cnt * (cnt - 1) // 2 # n_C_2 2つ選ぶ組み合わせ
 
print(ans)


### FIXED CODE ###

S = input()
N = len(S)

num = [0] * 2019
num[0] = 1
now, ans = 0, 0
_10 = 1

for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % 2019
    _10 *= 10
    _10 %= 2019
    ans += num[now]
    num[now] += 1
 
print(ans)
### BUGGY CODE ###

BUFSIZE = 50
D = int(input())
C = list(map(int, input().split()))

c0 = sum(C)
Q = [(0, [], 0, [0]*26)]

for d in range(D):
    S = list(map(int, input().split()))
    Q2 = []
    
    for q in Q:
        sc, ts, c1, lasts = q
        c2 = c1 + c0

        for t in range(26):
            c3 = c2 - (d + 1 - lasts[t])*C[t]
            lasts2 = lasts[:]
            lasts2[t] = d+1
            Q2.append((sc + S[t] - c3, [ts, t], c3, lasts2))

    sizeOfQ2 = len(Q2)
    Q = sorted(Q2, reverse=True)[:min(sizeOfQ2, BUFSIZE)]

# print(Q[0][0])
T = []
ts = Q[0][1]

for d in range(D):
    T.append(ts[1] + 1)
    ts = ts[0]

for t in reversed(T):
    print(t)







### FIXED CODE ###

BUFSIZE = 30
D = int(input())
C = list(map(int, input().split()))

c0 = sum(C)
Q = [(0, [], 0, [0]*26)]

for d in range(D):
    S = list(map(int, input().split()))
    Q2 = []
    
    for q in Q:
        sc, ts, c1, lasts = q
        c2 = c1 + c0

        for t in range(26):
            c3 = c2 - (d + 1 - lasts[t])*C[t]
            lasts2 = lasts[:]
            lasts2[t] = d+1
            Q2.append((sc + S[t] - c3, [ts, t], c3, lasts2))

    sizeOfQ2 = len(Q2)
    Q = sorted(Q2, reverse=True)[:min(sizeOfQ2, BUFSIZE)]

# print(Q[0][0])
T = []
ts = Q[0][1]

for d in range(D):
    T.append(ts[1] + 1)
    ts = ts[0]

for t in reversed(T):
    print(t)
### BUGGY CODE ###

n,m=map(int,input().split())
for i in reversed(range(m//n+1)):
    if m%i==0:print(i);break

### FIXED CODE ###

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

ans = 1
for i in range(1,int(M ** 0.5) + 1):
    if M % i == 0:
        if i >= N:
            ans = max(ans, M // i)
        if M // i >= N:
            ans = max(ans, i)
print(int(ans))
### BUGGY CODE ###

# https://atcoder.jp/contests/agc019/tasks/agc019_b
A = input()

ans = set({A})
n = len(A)
for i in range(n):
    for j in range(i + 1, n):
        new_A = A[:i] + A[i:j+1][::-1] + A[j+1:]
        # print(i, j, A, A[i:j+1], new_A)
        ans.add(new_A)

print(len(ans))

### FIXED CODE ###

# https://atcoder.jp/contests/agc019/tasks/agc019_b
from collections import defaultdict

A = input()
n = len(A)
cA = defaultdict(int)

for ch in A:
    cA[ch] += 1

all_num = 1 + n * (n - 1) // 2

for _, v in cA.items():
    all_num -= v * (v - 1) // 2

print(all_num)