Harryxun/stf_run huggingface dataset:
from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
DIRC = [(-1, 0), (0, 1), (1, 0), (0, -1)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        for di, dj in DIRC:
            x, y = i+di, j+dj
            if x < 0 or y < 0 or n <= x or n <= y:
                continue
            c = cost[v]+exist[v]
            if cost[to_v(x, y)] <= c:
                continue
            cost[to_v(x, y)] = c
            next_v.append((x, y))


ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)

### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        if 0 < i:
            v2 = v-n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if i < n-1:
            v2 = v+n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if 0 < j:
            v2 = v-1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if j < n-1:
            v2 = v+1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)
res, tmp = 0, 0
for c in s:
    if c == 'R':
        tmp += 1
        res = max(res, tmp)
    else:
        tmp = 0

print(res)

### FIXED CODE ###

s = input().strip()
res, tmp = 0, 0

for c in s:
    if c == 'R':
        tmp += 1
        res = max(res, tmp)
    else:
        tmp = 0

print(res)
t,k,a,o = map(int,input().split())
taka=int(a//k)
aoki=int(t//o)
if taka<=aoki:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

x,y = map(int,input().split())
if x<=y:
    print('unsafe')
else:
    print('safe')
from functools import lru_cache


CHECK = False

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

MOD = 10 ** 9 + 7


@lru_cache(maxsize=None)
def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


if CHECK:
    fact = [1]
    for i in range(1, 2 * N + 1):
        fact.append((fact[-1] * i) % MOD)

    def nCr(n, r, p=MOD):
        # Modulo binomial coefficients
        return (fact[n] * modInverse(fact[r], p) * modInverse(fact[n - r], p)) % p


if N - 1 <= K:
    # Any combo is achievable so this is stars and bars
    # N people into N rooms, which means N - 1 dividers
    stars = N
    bars = N - 1
    print(nCr(stars + bars, bars))
else:
    # Group by number of empty rooms
    # With K moves there can only be at most K empty rooms
    # Max of N - 1 empty rooms in general
    assert K + 1 < N
    tot = 0
    comb1 = 1
    comb2 = 1
    for numEmpty in range(K + 1):
        way3 = comb1 * comb2
        if CHECK:
            numNonEmpty = N - numEmpty
            stars = numEmpty  # Everyone moving into an occupied room
            bars = numNonEmpty - 1  # Number of dividers
            way1 = nCr(stars + bars, bars) * nCr(N, numEmpty)

            way2 = nCr(N, numEmpty) * nCr(N - 1, numEmpty)

            assert way1 % MOD == way2 % MOD == way3 % MOD
        tot += way3

        j = numEmpty + 1
        invJ = modInverse(j, MOD)
        comb1 = (N + 1 - j) * comb1 * invJ % MOD
        comb2 = (N - j) * comb2 * invJ % MOD
    print(tot % MOD)


### FIXED CODE ###

from functools import lru_cache


CHECK = False

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

MOD = 10 ** 9 + 7


@lru_cache(maxsize=None)
def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


if N - 1 <= K or CHECK:
    fact = [1]
    for i in range(1, 2 * N + 1):
        fact.append((fact[-1] * i) % MOD)

    def nCr(n, r, p=MOD):
        # Modulo binomial coefficients
        return (fact[n] * modInverse(fact[r], p) * modInverse(fact[n - r], p)) % p


if N - 1 <= K:
    # Any combo is achievable so this is stars and bars
    # N people into N rooms, which means N - 1 dividers
    stars = N
    bars = N - 1
    print(nCr(stars + bars, bars))
else:
    # Group by number of empty rooms
    # With K moves there can only be at most K empty rooms
    # Max of N - 1 empty rooms in general
    assert K + 1 < N
    tot = 0
    comb1 = 1
    comb2 = 1
    for numEmpty in range(K + 1):
        way3 = comb1 * comb2
        if CHECK:
            numNonEmpty = N - numEmpty
            stars = numEmpty  # Everyone moving into an occupied room
            bars = numNonEmpty - 1  # Number of dividers
            way1 = nCr(stars + bars, bars) * nCr(N, numEmpty)

            way2 = nCr(N, numEmpty) * nCr(N - 1, numEmpty)

            assert way1 % MOD == way2 % MOD == way3 % MOD
        tot += way3

        j = numEmpty + 1
        invJ = modInverse(j, MOD)
        comb1 = (N + 1 - j) * comb1 * invJ % MOD
        comb2 = (N - j) * comb2 * invJ % MOD
    print(tot % MOD)
n,x=map(int,input().split())
l=[0]
for i in range(n+1):
  l.append(2**(i+1)-1)
m=[0]
for i in range(n+1):
  m.append(2**(i+2)-3)
c=0
for i in range(n,-1,-1):
  if x<2**(i+1)-1:
    x-=1
  elif x==2**(i+1)-1:
    c+=l[i]+1
    x=0
  elif x>2**(i+1)-1:
    c+=l[i]+1
    elif x==m[i+1]:
      x-=1
    x=x-(2**(i+1)-1)
print(c)

### FIXED CODE ###

n,x=map(int,input().split())
l=[]
for i in range(n+1):
  l.append(2**(i+1)-1)
m=[]
for i in range(n+1):
  m.append(2**(i+2)-3)
c=0
for i in range(n,-1,-1):
  if x<2**(i+1)-1:
    x-=1
  elif x==2**(i+1)-1:
    if i!=0:
      c+=l[i-1]+1
    elif i==0:
      c+=1
    x=0
  elif x>2**(i+1)-1:
    if i!=0:
      c+=l[i-1]+1
    elif i==0:
      c+=1
    elif x==m[i]:
      x-=1
    x=x-(2**(i+1)-1)
print(c)
n=int(input())
A=[]
X=[]
Y=[]
x=[]
y=[]
l=[1]*n
for i in range(n):
  a=int(input)
  A.append(a)
  for j in range(a):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
  X.append(x)
  Y.append(y)
  
c=0
for i in range(n):
  for j in range(i,n):
    if l[j]==0:continue
    for k in range(A[i]):
    　　l[X[j][k]] *= Y[j][k]
  if c<l.count(1):
    c=l.count(1) 
  
        
  
print(c)  
  
  
  
  
  
  
  
  
  
  
  
  
  

### FIXED CODE ###

n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[0]*a
  y=[0]*a
  for j in range(a):
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
s=0
for i in range(2**n):
  c=0
  d=0
  B=[0]*n
  for j in range(n):
    if((i >> j) & 1):
      c=c+1
      B[j]=1
  for k in range(n):
    if B[k]==1:
      for j in range(A[k]):
        if Y[k][j]!=B[X[k][j]-1]:
          d=-1
          break
    if d<0:
      break
  if s<c and d==0:
    s=c
      
      
print(s)
# coding: utf-8
# Your code here!

N = int(input())
A = list(map(int, input().split()))
A.sort()                  #エラトステネスの篩にかけるためソート
A = list(set(A))
Amax = A[-1]              #最大値
dp = [1]*(Amax+1)         #Aの最大値までのエラトステネスの篩を作る
ans = 0
# print(A)
if len(A)!=1:
    for i in range(len(A)):
      p = A[i]
      if dp[p] == 1:          #A[i]がA[j]の倍数でないかをエラトステネスの篩でチェック
        
        for q in range(Amax//p+1):
          dp[p*q] = 0         #A[i]の倍数をすべて0にする
        # print(dp)
      else:
          ans+=1
        #   print(A[i])
    #     if A[i] != A[i+1]: 
    #       ans += 1            #A[i]が重複していなければカウント
    #     print(ans)
    # if dp[Amax] == 1:         #重複チェック時にレンジオーバーするためAmaxだけ別で判定 
    #   ans += 1
    print(len(A)-ans)
else:
    print(0)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()                  #エラトステネスの篩にかけるためソート
Amax = A[-1]
dp = [1]*(Amax+1)         #Aの最大値までのエラトステネスの篩を作る。
ans = 0
for i in range(len(A)-1):
  p = A[i]
  if dp[p] == 1:          #A[i]がA[j]の倍数でないかをエラトステネスの篩でチェック
    for q in range(Amax//p+1):
      dp[p*q] = 0         #A[i]の倍数をすべて0にする
    if A[i] != A[i+1]: 
      ans += 1            #A[i]が重複していなければカウント
if dp[Amax] == 1:         #重複チェック時にレンジオーバーするためAmaxだけ別で判定 
  ans += 1
print(ans)
def dfs_v(u):
  color[u] = 1
  t += 1
  d[u] = t
  for v in range(n):
    if M[u][v] == 1 and color[v] == 0:
      dfs_v(v)
  color[u] = 2
  t += 1
  f[u] = t

def dfs():
  t = 0
  for u in range(n):
    if color[u] == 0:
      dfs_v(u)
  for u in range(n):
    print u+1, d[u], f[u]

n = input()

color = [0 for i in range(100)]
d = [0 for i in range(100)]
f = [0 for i in range(100)]
M = [0 for i in range(n)]0 for j in range(n)]

for i in range(n):
  u, k = map(int, raw_input().split())
  for j in range(k):
   v = input()
   M[u-1][v-1] = 1

dfs()
    

### FIXED CODE ###

n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    col[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()
N = int(input())

for i in range(1,9):
    for j in range(1,9):
        if N % i == 0 and N % j == 0:
            print("Yes")
            break
        else:
            print("No")
            break
    break


### FIXED CODE ###

A,B=map(int,input().split())
if A <= 9 and B <= 9:
    print(A*B)
else:
    print(-1)
S,T = input().split()
A,B = map(int,input().split())
U = input()

if S == U:
  print({},{}).format(A-1,B)
else:
  print({},{}).format(A,B-1)

### FIXED CODE ###

S,T = input().split()
A,B = map(int,input().split())
U = input()
 
if S == U :
    print("{} {}".format(A-1,B))
else :
    print("{} {}".format(A,B-1))
N, A, B = map(int, input().split())

a = "b"*A
b = "r"*B

l = ""
for i in range(1,int(N/(A+B)+1)+1):
    if N - len(l)  > (A+B):
        l = l + a + b
    elif N - len(l) < (A):
        l = l + a[1:(N - len(l)+1)]

l[0:N].count("b")

### FIXED CODE ###

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

n = N // (A + B)
mod = N % (A + B)
 
if mod >= A:
    print(A * n + A)
else:
    print(A * n + mod)
n = int(input())
d = list(map(int,input().split()))

t = d.sort()

a = t[(n/2)-1]
b = t[(n/2)]

print(b-a)

### FIXED CODE ###

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

d.sort()

a = d[int(n/2)-1]
b = d[int(n/2)]

print(b-a)
def f(x,n):
	if x == 1: return [n];
	if x % 2 == 1:
		return f(x >> 1,n + 1) + [n]
	else:
		return [n] + f(x - 1,n + 1)

n = input()
p += range(1,len(p) + 1)
print ' '.join(list(map(str,p)))



### FIXED CODE ###

def f(x,n):
	if x == 1: return [n];
	if x % 2 == 1:
		return f(x >> 1,n + 1) + [n]
	else:
		return [n] + f(x - 1,n + 1)

def g(x,n):
	if x == 1: return [n];
	if x % 2 == 1:
		return g(x >> 1,n + 1) + [n]
	else:
		return g(x - 1,n + 1) + [n]

n = input()
p = f(n,1) + g(n,1)
print len(p)
print ' '.join(list(map(str,p)))
S, T ＝ map(str, input().split())
A, B ＝ map(int, input().split())
U ＝ input()

if S ＝＝ U:
    A ＝ A － 1
else：
    B ＝ B － 1
  
print(A)
print(B)

### FIXED CODE ###

S, T = map(str, input().split())
A, B = map(int, input().split())
U = input()

if S == U:
    A = A - 1 
else:
    B = B - 1 

print(str(A) + " " + str(B))
import math

MOD = 1000000007
N = int(input())
A = list(map(int,input().split()))
print(math.gcd(5,4))

### FIXED CODE ###

def lcm(X,Y):
    x=X
    y=Y
    if y>x:
        x,y=y,x
    while x%y!=0:
        x,y=y,x%y
    return X*Y//y

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

LCM = A[0]
for i in range(0,N-1,1):
    LCM = lcm(LCM,A[i+1])
B = [0 for i in range(0,N,1)]
for i in range(0,N,1):
    B[i]= (LCM%MOD)*pow(A[i],MOD-2,MOD)%MOD

ans = 0
for i in range(0,N,1):
    ans = (B[i] + ans)%MOD

print(ans)
N = int(input())
# calculate primes by sieve
primes = list(range(2, N + 1))
prime_index = 0
n = primes[prime_index]
while n**2 <= N:
    primes = list(filter(lambda x: x == n or x % n != 0, primes))
    prime_index += 1
    n = primes[prime_index]
# calculate exponents
exponents = [0 for _ in range(len(primes))]
for n in range(2, N + 1):
    for prime_index, prime in enumerate(primes):
        exponent = 0
        tmp = n
        while tmp % prime == 0:
            tmp //= prime
            exponent += 1
        exponents[prime_index] += exponent
# calculate answer
const = 10**9 + 7
answer = 1
for e in exponents:
    answer = answer * (e + 1)
    answer %= const
print(answer)

### FIXED CODE ###

N = int(input())
if N == 1:
    print(1)
    exit()
# calculate primes by sieve
primes = list(range(2, N + 1))
prime_index = 0
n = primes[prime_index]
while n**2 <= N:
    primes = list(filter(lambda x: x == n or x % n != 0, primes))
    prime_index += 1
    n = primes[prime_index]
# calculate exponents
exponents = [0 for _ in range(len(primes))]
for n in range(2, N + 1):
    for prime_index, prime in enumerate(primes):
        exponent = 0
        tmp = n
        while tmp % prime == 0:
            tmp //= prime
            exponent += 1
        exponents[prime_index] += exponent
# calculate answer
const = 10**9 + 7
answer = 1
for e in exponents:
    answer = answer * (e + 1)
    answer %= const
print(answer)
import random

X,N = input().split()
X,N = int(X),int(N)

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

if len(P) == 0:
    print(X)    
else:
    L = list(range(max(0,X-N),min(101,X+N)))

    if X+N <= 100:
        L.append(X+N)

    for i in range(N):
        if P[i] in L:
            L.remove(P[i])

    #print(L)

    while len(L) > 2:
        rand = random.randint(1,len(L)-2)
        if L[rand] == X:
            break
        elif L[rand] > X:
            L = L[0:rand+1]
        else:
            L = L[rand:len(P)]

    if X in L:
        print(X)
    else:
        if abs(L[0]-X) > abs(L[1]-X):
            print(L[1])
        else:
            print(L[0])

### FIXED CODE ###

import random

X,N = input().split()
X,N = int(X),int(N)

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

if len(P) == 0:
    print(X)    
else:
    L = list(range(max(0,X-N),min(102,X+N)))

    if X+N <= 101:
        L.append(X+N)

    for i in range(N):
        if P[i] in L:
            L.remove(P[i])

    while len(L) > 2:
        rand = random.randint(1,len(L)-2)
        if L[rand] == X:
            break
        elif L[rand] > X:
            L = L[0:rand+1]
        else:
            L = L[rand:len(L)]

    if X in L:
        print(X)
    elif len(L) == 1:
        print(L[0])
    else:
        if abs(L[0]-X) > abs(L[1]-X):
            print(L[1])
        else:
            print(L[0])
while True:
    H, W =[int(i) for i in input().split ]
    if H == W == 0:
       break

   for h in range(H):
        for w in range(W):
            print('*', end='')
        else:
            print('+', end='')

        print()

    print()

### FIXED CODE ###

while True:
    H, W = [int(i) for i in input().split()]
    if H == W == 0:
        break
     
    for h in range(H):
        for w in range(W):
            if h == 0 or h == H-1 or w == 0 or w == W - 1:
                print('#', end='')
            else:
                print('.', end='')
        print()
     
    print()
from collections import deque

h,w = map(int,input().split())
maze = []

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [ [99999999]*w for _ in range(i) ]
            
            dq = deque()
            y=i
            x=j
            d=0
            
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                dist[y][x]=d
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)


### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
maze = []

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [ [99999999]*w for _ in range(h) ]
            
            dq = deque()
            y=i
            x=j
            d=0
            dist[y][x]=0
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dist[y+m[1]][x+m[0]]=d+1
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)
n = int(input())

if n == 1:
  print('Hello World')
  exit()
else if n == 2:
  a = int(input())
  b = int(input())
  print(a+b)

### FIXED CODE ###

n = int(input())

if n == 1:
  print('Hello World')
  exit()
elif n == 2:
  a = int(input())
  b = int(input())
  print(a+b)
N, M = map(int, input().split())
broken_lst = []
for _ in range(M):
    broken_lst.append(int(input()))

counter_arr = [0]*(N+1)

counter_arr[0] = 1
next_broken = -1
if len(broken_lst) != 0:
    next_broken = broken_lst.pop(0)
last_broken = broken_lst[0]

for i in range(0, N-1):
    flug = 0
    if i+1 == next_broken:
        flug = 1
#        print("p0", i, counter_arr)
    elif i+1 == last_broken:
        pass
#        print("p1",i, counter_arr)
    else:
        counter_arr[i+1] += counter_arr[i]
        counter_arr[i+1] %= 10**9 + 7
#        print("p2",i,  counter_arr)

    if i + 2 == next_broken or i + 2 == last_broken:
        flug = 1
#        print("p3",i, counter_arr)
    else:
        counter_arr[i+2] += counter_arr[i]
        counter_arr[i+2] %= 10**9 + 7
#        print("p4",i, counter_arr)
    
    if flug == 1:
        last_broken = next_broken
        if len(broken_lst) != 0:
            next_broken = broken_lst.pop(0)

if last_broken != N - 1:
    counter_arr[-1] += counter_arr[-2]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])


### FIXED CODE ###

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

counter_arr = [0]*(N+1)

counter_arr[0] = 1
next_broken = -1
if len(broken_lst) != 0:
    next_broken = broken_lst.pop(0)
last_broken = -1

for i in range(0, N-1):
    flug = 0
    if i+1 == next_broken:
        flug = 1
#        print("p0", i, counter_arr)
    elif i+1 == last_broken:
        pass
#        print("p1",i, counter_arr)
    else:
        counter_arr[i+1] += counter_arr[i]
        counter_arr[i+1] %= 10**9 + 7
#        print("p2",i,  counter_arr)

    if i + 2 == next_broken:
        flug = 1
#        print("p3",i, counter_arr)
    else:
        if i == 0 and len(broken_lst) != 0:
            if broken_lst[0] == 2 and next_broken == 1:
                continue
        counter_arr[i+2] += counter_arr[i]
        counter_arr[i+2] %= 10**9 + 7
#        print("p4",i, counter_arr)
    
    if flug == 1:
        last_broken = next_broken
        if len(broken_lst) != 0:
            next_broken = broken_lst.pop(0)

if last_broken != N - 1:
    counter_arr[-1] += counter_arr[-2]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])
from sys import stdin


def get_result(data):
    S = data[0]
    int_S = int(S)
    mod_all_bit = [0] * 2018
    mod_all_bit[0] = 1
    for i in range(len(S)):
        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)
import sys
import bisect

f = sys.stdin

#n = int(f.readline())
a = list(map(int,f))
a[0] = 0
for i in range(1,len(a)):
    a[i] += a[i - 1]

sum_a = a[-1]
third = sum_a // 3

ret = []

for i in range(bisect.bisect_left(a, third)):
    nick1 = bisect.bisect_left(a, a[i] + third,lo=i)
    
    for ni1 in (nick1-1,nick1):
        second = min(third,(sum_a - (a[ni1] - a[i])) // 2)
        nick2 = bisect.bisect_left(a, a[ni1] + second,lo=nick)
        for ni2 in (nick2-1,nick2):
            if len(a) <= ni2:
                continue
            piece1 = a[ni1] - a[i]
            piece2 = a[ni2] - a[ni1]
            piece3 = sum_a - piece1 - piece2
            ret.append(min(piece1,piece2,piece3))
print(max(ret))

### FIXED CODE ###

import sys

f = sys.stdin


def bisect(a,v):
    l,r = 0,len(a)-1
    
    while l != r:
        m = (l + r) // 2
        if a[m] < v:
            l = m + 1
        else:
            r = m
    return l

#n = int(f.readline())
a = list(map(int,f))
a[0] = 0
for i in range(1,len(a)):
    a[i] += a[i - 1]

sum_a = a[-1]
third = sum_a // 3

ret = []

for i in range(bisect(a, third)):
    nick1 = bisect(a, a[i] + third)
    
    for ni1 in (nick1-1,nick1):
        second = (sum_a - (a[ni1] - a[i])) // 2
        second = min(second,third)
        nick2 = bisect(a, a[ni1] + second)
        for ni2 in (nick2-1,nick2):
            if len(a) <= ni2:
                break
            piece1 = a[ni1] - a[i]
            piece2 = a[ni2] - a[ni1]
            piece3 = sum_a - piece1 - piece2
            ret.append(min(piece1,piece2,piece3))
print(max(ret))
A="abcdefghijklmnopqrstuvwxyz"
n=int(input())-1
name=[]
while n>0:
    temp=n%26
    name.append(temp)
    n//=26
length=len(name)
for i in range(length-1):
    print(A[name[length-i-1]-1],end="")
print(A[name[0]])

### FIXED CODE ###

A="abcdefghijklmnopqrstuvwxyz"
n=int(input())
i=1
while n-26**i>0:
    n-=26**i
    i+=1
name=[]
n-=1
for j in range(i):
    temp=n%26
    name.append(A[temp])
    n//=26
for k in name[::-1]: print(k,end="")
l = input()
dp1 = [0] * (len(l)+1)
dp2 = [0] * (len(l)+1)
 
dp1[1] = 1
dp2[1] = 2
if l == '1':
  print(3)
  exit()
for i in range(1, len(l)):
  if l[i] == '0':
  	dp1[i+1] = 3 * dp1[i] + 1 * dp2[i]
    dp1[i+1] %= 1000000007
  	dp2[i+1] = dp2[i]
  else:
    dp1[i+1] = 3 * dp1[i] + 3 * dp2[i]
    dp1[i+1] %= 1000000007
    dp2[i+1] = 3 * dp2[i]
    dp2[i+1] %= 1000000007
print(dp1[len(l)] % 1000000007)

### FIXED CODE ###

l = input()
dp1 = [0] * (len(l)+1)
dp2 = [0] * (len(l)+1)
 
dp1[1] = 1
dp2[1] = 2
if l == '1':
  print(3)
  exit()
for i in range(1, len(l)):
  if l[i] == '0':
    dp1[i+1] = 3 * dp1[i]
    dp1[i+1] %= 1000000007
    dp2[i+1] = dp2[i]
  else:
    dp1[i+1] = 3 * dp1[i] + dp2[i]
    dp1[i+1] %= 1000000007
    dp2[i+1] = 2 * dp2[i]
    dp2[i+1] %= 1000000007
print((dp1[len(l)] + dp2[len(l)]) % 1000000007)