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

#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([0,i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

inf=float("inf")
 
t=[[inf for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[1]][txy[2]]=0

while q:
    d,y,x=q.pop(0)
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]>t[y][x]+1:
            t[ny][nx]=t[y][x]+1
            q.append([d+1,ny,nx])
a=0
for res in t:
    a=max(a,max(res))
print(a)

### FIXED CODE ###

#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

from collections import deque

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

t=[[-1 for _ in range(w)] for _ in range(h)]
q=deque()
for txy in sxy:
    q.append(txy)
    t[txy[0]][txy[1]]=0

count=0
while q:
    y,x=q.popleft()
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==-1:
            t[ny][nx]=t[y][x]+1
            q.append([ny,nx])
a=0
for i in range(h):
    for j in range(w):
        a=max(a,t[i][j])
print(a)
### BUGGY CODE ###

n,q = map(int,input().split())
s = list(input())
check = [0]*n
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        check[i+1] = 1
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for j in range(l,r):
        ans += check[j]
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int,input().split())
s = list(input())
check = [0]*n
const = 0
for i in range(n-1):
    check[i] = const
    if s[i] == 'A' and s[i+1] == 'C':
        check[i+1] = const + 1
        const += 1
        i += 1
check[-1] = const
for i in range(q):
    l,r = map(int,input().split())
    print(check[r-1]-check[l-1])
### BUGGY CODE ###

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

ans=-float('inf')

def get_loop_score(start): # return loop len and its loop score
    now_p=0
    visited=set()
    nxt=p[start]-1

    while True:
        nxt=p[nxt]-1
        if nxt in visited:
            break
        visited.add(nxt)
        now_p+=c[nxt]
    return now_p

def simulate(start,nokori): # ret max possible score
    now_p=0
    nxt=p[start]-1
    cnt=0
    p_lis=[]


    while True:
        nxt=p[nxt]-1
        visited.add(nxt)
        now_p+=c[nxt]
        p_lis.append(now_p)
        cnt+=1
        if cnt==nokori:
            break

    return max(p_lis)

for i in range(n):
    p_lis=[]

    cnt=0
    now_p=0
    nxt=p[i]-1

    visited=set()

    while True:
        now_p+=c[nxt]
        nxt=p[nxt]-1
        p_lis.append(now_p)

        cnt+=1
        if cnt==k:
            break

        if k>5010 and nxt in visited:
#            print(visited)
            break
        visited.add(nxt)

    if cnt!=k: # loop detected
#        print(i,p_lis)
        nokori = k-cnt
        loop_score=get_loop_score(nxt)
        if loop_score <= 0: # no loop
            nokori=len(visited)
        else: # loop as much as possible
            loops = nokori//len(visited) - 1
            now_p+= loops*loop_score
            nokori = loops*len(visited)

#        print("loop score:",loop_score)
        score = simulate(nxt,nokori)
        p_lis.append(score)

#    print(i,max(p_lis))

    ans=max(ans,max(p_lis))

print(ans)

### FIXED CODE ###

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

def sim(start,mx): # simulate mx step from start, returns max_score
    if mx==0:
        return 0
    now_p=0
    nxt=p[start]-1
    cnt=0
    p_lis=[]

    while True:
        nxt=p[nxt]-1
        now_p+=c[nxt]
        p_lis.append(now_p)
        cnt+=1
        if cnt==mx:
            break

    return max(p_lis)

visited_p=set() # already checked flag
cycle_score=[] # cycle loop score
cycle_points=[]
now_cycle=0

for i in range(n):
    if i in visited_p:
        continue
    visited_p.add(i)
    now_p=0
    nxt=p[i]-1
    visited=set()
    while True:
        nxt=p[nxt]-1
        visited_p.add(nxt)
        if nxt in visited:
            break
        visited.add(nxt)
        now_p+=c[nxt]
    cycle_score.append(now_p)
    cycle_points.append(list(visited))

ans=-float('inf')

for c_num in range(len(cycle_score)):
#    print(c_num,cycle_score[c_num],cycle_points[c_num])
    cycle_len=len(cycle_points[c_num])
    for start in cycle_points[c_num]:

        if cycle_score[c_num]<0: # no loop, just check min(loop_len,k)
            score = sim(start,min(cycle_len,k))
            ans=max(ans,score)

        else: # loop as many as possible
            loop_num = max(0,(k // cycle_len) - 1)
            nokori=k-loop_num*cycle_len
            score = sim(start,nokori) + loop_num*cycle_score[c_num]
            ans=max(ans,score)

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

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

    count = 0
    for rr in range(n//r + 1):
        for gg in range((n-rr*r)//g + 1):
            for bb in range((n-rr*r-gg*g)//b + 1):
                if (rr*r + gg*g + bb*b) == n:
                    count += 1
    print(count)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    count = 0
    for rr in range(n//r + 1):
        for gg in range((n-rr*r)//g + 1):
            if (n-rr*r-gg*g) % b == 0:
                count += 1
    print(count)

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

from sys import stdin
import math
import itertools
import re
import sys
sys.setrecursionlimit(10**8)
 
 
def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]
 
dp = {}
T = {}
 
def solve(input_string):
    N, Q = map(int, input_string[0].split())
    S = input_string[1]
    intMatrix = makeIntMatrix(input_string[2:])
    #print(input_string[2:])
    #for i in range(Q):
    for line in intMatrix:
        t=[0]*(N+1)
        for i in range(N):
            t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
        l, r = line
        #print(l, r)
        #print(S[l:r+1])
        #cnt = len(re.findall(r'AC', S[l-1:r]))
        #totalCnt = cntAC(L, R, S)
        totalCnt = t[r-1] - t[l-1]
        print(totalCnt)
    return
 

"""
wrong answer
def cntAC(l, r, D, S, cnt):
    global dp
    global T
    if r-l == D+1:
        return cnt
    if str(l)+str(r) not in T:
        T[str(l)+str(r)] = S[l-1:r]
        t = T[str(l)+str(r)]
    if str(l)+str(r) not in dp:
        #print(t)
        dp[str(l)+str(r)] = len(t.split('AC'))-1
        cnt = dp[str(l)+str(r)]
        return cntAC(l-1, r, D, S, cnt)
    else:
        cnt = dp[str(l)+str(r)]
        return cntAC(l-1, r, D, S, cnt)
"""
 

"""
wrong answer
def cntAC(L, r, S):
    global dp
    global T
    for l in range(L, r)[::-1]:
        if str(l)+str(r) not in T:
            T[str(l)+str(r)] = S[l-1:r]
            t = T[str(l)+str(r)]
        else:
            t = T[str(l)+str(r)]
        if str(l)+str(r) not in dp:
            dp[str(l)+str(r)] = len(t.split('AC'))-1
            cnt = dp[str(l)+str(r)]
        else:
            cnt = dp[str(l)+str(r)]
    return cnt
"""
 
def cntAC(L, R, S):
    cnt = 0
    for l in range(L, R):
        t = S[l-1:l+1]
        cnt +=  1 if t == 'AC' else 0
    return cnt

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    #print(answer)
 
 
if __name__ == '__main__':
    main()


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t=[0]*(N+1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

import numpy as np

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

ans = 0
for i in range(N):
    tmp_A = A + A[i]
    tmp_B = np.concatenate([np.zeros(i),np.arange(N-i)])
    C = tmp_B - tmp_A
    ans += np.count_nonzero(C == 0)

print(ans)

### FIXED CODE ###

import numpy as np
from collections import Counter

N = int(input())
A = np.array(list(map(int, input().split())))
B = np.arange(N) + 1

s = A + B
m = B - A

s_ct = Counter(s)
m_ct = Counter(m)

ans = 0
for i in s_ct:
    ans += s_ct[i] * m_ct[i]

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

def main():
    r1, c1, r2, c2 = map(int, raw_input().split())
    MOD = 10 ** 9 + 7


    # 階乗 & 逆元計算
    factorial = [1]
    inverse = [1]
    for i in range(1, r2 + c2 + 10):
        factorial.append(factorial[-1] * i % MOD)
        inverse.append(pow(factorial[-1], MOD - 2, MOD))


    # 組み合わせ計算
    def nCr(n, r):
        if n < r or r < 0:
            return 0
        elif r == 0:
            return 1
        return factorial[n] * inverse[r] * inverse[n - r] % MOD


    ans = 0
    for r in range(r1, r2 + 1):
        ans += ((nCr(r + c2 + 1, r + 1) % MOD) - (nCr(r + c1, r + 1) % MOD)) % MOD
        ans %= MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    r1, c1, r2, c2 = map(int, raw_input().split())
    MOD = 10 ** 9 + 7

    mod = 10 ** 9 + 7  # 出力の制限
    N = 10 ** 4
    g1 = [1, 1]  # 元テーブル
    g2 = [1, 1]  # 逆元テーブル
    inverse = [0, 1]  # 逆元テーブル計算用テーブル

    for i in range(2, r2 + c2 + 10):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

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


    ans = 0
    for r in range(r1, r2 + 1):
        ans += ((cmb(r + c2 + 1, r + 1, MOD) % MOD) - (cmb(r + c1, r + 1, MOD) % MOD)) % MOD
        ans %= MOD

    print(ans % MOD)


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

MOD = 998244353
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * (m.i if isinstance(m, mint) else m) % MOD)
    def __sub__(self, m):
        t = self.i - (m.i if isinstance(m, mint) else (m % MOD))
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        return mint(pow(i, m, MOD))
    def __truediv__(self, m):
        return mint(self.i * pow(m, MOD - 2, MOD) % MOD)
    def __repr__(self):
        return repr(self.i)


n, s = map(int, input().split())
dp = [mint(0)] * (s + 1)
dp[0] = mint(2) ** n
i2 = mint(2) ** (MOD-2)
for a in map(int, input().split()):
    for i in range(s, -1, -1):
        if a + i <= s:
            dp[a + i] += dp[i] * i2
print(dp[s])


### FIXED CODE ###

MOD = 998244353
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * (m.i if isinstance(m, mint) else m) % MOD)
    def __sub__(self, m):
        t = self.i - (m.i if isinstance(m, mint) else (m % MOD))
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        return mint(pow(i, m, MOD))
    def __truediv__(self, m):
        return mint(self.i * pow(m, MOD - 2, MOD) % MOD)
    def __repr__(self):
        return repr(self.i)


n, s = map(int, input().split())
dp = [mint(0)] * (s + 1)
dp[0] = mint(2) ** n
i2 = mint(2) ** (MOD-2)
for a in map(int, input().split()):
    for i in range(s, -1, -1):
        if a + i <= s:
            dp[a + i] += dp[i] * i2
print(dp[s])
### BUGGY CODE ###

from itertools import combinations as cmb
n=int(input())
s=input()
sss=[]
for i in range(len(s)):
    sss.append(s[i])
combiset=set(cmb(sss,3))
print(len(combiset))

### FIXED CODE ###

n=int(input())
s=list(map(int,list(input())))
ans=0
for i in range(10):
    try:
        ss=s[s.index(i)+1:]
        for j in range(10):
            try:
                sss=ss[ss.index(j)+1:]
                for k in range(10):
                    if k in sss:ans+=1
            except:pass
    except:pass

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

N,M = map(int,input().split(' '))
ans = 1
P = M//N
for i in range(P):
    ans = P - i
    if M%ans == 0:
        break
print(ans)

### FIXED CODE ###

import math


def divisor(num):
    if num < 0:
        return [0,]
    elif num == 1:
        return [1,]
    else:
        divisor_list =[1,]
        for i in range(2, int(math.sqrt(num) + 1)):
            if num % i== 0:
                divisor_list.append(i)
        return divisor_list


N,M = map(int,input().split(' '))
P = M // N
divisor_list = divisor(M)

for i in reversed(range(len(divisor_list))):
    num = M // divisor_list[i]
    divisor_list.append(num)

for i in reversed(range(len(divisor_list))):
    if divisor_list[i] <= P:
        print(divisor_list[i])
        break
### BUGGY CODE ###

from collections import deque
N = int(input())
node = [[]for i in range(N)]
side = []
ans = [0]*(N-1)
for i in range(N-1):
    a,b = map(int,input().split())
    side.append([a-1,b-1])
    node[a-1].append(i)
    node[b-1].append(i)

K = max(len(i) for i in node)
print(K)

queue = deque([0])

while queue:
    q = queue.popleft()
    use = [0]*(K+1)
    for i in node[q]:
        use[ans[i]] = 1
    p = 1
    for i in node[q]:
        if ans[i] == 0:
            while use[p]:
                p += 1
            ans[i] = p
            use[p] = 1
            s = side[i]
            queue.append(s[(s.index(q)+1)%2])

for i in ans:
    print(i)

### FIXED CODE ###

from collections import deque
N = int(input())
node = [[]for i in range(N)]
side = []
count = [0]*N
ans = [0]*(N-1)
closed = [0]*N
for i in range(N-1):
    a,b = map(int,input().split())
    side.append([a-1, b-1])
    node[a-1].append(i)
    node[b-1].append(i)
    count[a-1] += 1
    count[b-1] += 1

K = max(count)
print(K)

queue = deque([[0,K+1]])


while queue:
    q,m = queue.popleft()
    p = 1
    for i in node[q]:
        if p == m:
            p += 1
        if ans[i] == 0:
            ans[i] = p
            s = side[i]
            next = s[(s.index(q)+1)%2]
            if closed[next] == 0:
                queue.append([next,p])
                closed[next] = 1
            p += 1

for i in ans:
    print(i)
### BUGGY CODE ###

h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
def f(dh,dw):
  if s[dh][dw] == "#":
    a = 1
  else:
    a = 0
  if dh == h-1 and dw == w-1:
    return a
  elif dh == h-1:
    return a + f(dh,dw+1)
  elif dw == w-1:
    return a + f(dh+1,dw)
  else:
    return a + min(f(dh,dw+1),f(dh+1,dw))
print(f(0,0))

### FIXED CODE ###

h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
dp = [[h*w]*w for _ in range(h)]
if s[0][0] == "#":
  dp[0][0] = 1
else:
  dp[0][0] = 0
for i in range(h):
  for j in range(w):
    if i < h-1:
      if s[i][j]=="." and s[i+1][j]=="#":
        dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
      else:
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
    if j < w-1:
      if s[i][j]=="." and s[i][j+1]=="#":
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+1)
      else:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j])
print(dp[h-1][w-1])
### BUGGY CODE ###

N, M = map(int, raw_input().split(' '))
P = 1000000007

skip = []
for i in range(M):
    skip.append(int(raw_input()))


steps = [0] * (N + 2)
steps[0] = 1

for i in range(0, N):
    if i+1 not in skip:
        steps[i+1] += steps[i]
        steps[i+1] %= P

    if i+2 not in skip:
        steps[i+2] += steps[i]
        steps[i+2] %= P

print steps[N]


### FIXED CODE ###

N, M = map(int, raw_input().split(' '))
P = 1000000007

skip = []
for i in range(M):
    skip.append(int(raw_input()))

nums = set(range(N)) - set(skip)

steps = [0] * (N + 2)
steps[0] = 1

for i in nums:
    steps[i+1] = (steps[i+1] + steps[i]) % P
    steps[i+2] = (steps[i+2] + steps[i]) % P

print steps[N]
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
mod = 10**9+7
a = [0]+[int(i) for i in readline().split()]
b = [0]+[int(i) for i in readline().split()]
dp = [[0]*(m+1) for i in range(n+1)]
su = [[0]*(m+1) for i in range(n+1)]

dp[0][0] = 1
su[0][0] = 1
for i in range(1,n+1):
  su[i][0] = 1
for j in range(1,m+1):
  su[0][j] = 1
  
for i in range(1,n+1):
  for j in range(1,m+1):
    if a[i] == b[j]:
      dp[i][j] = su[i-1][j-1]
    else:
      dp[i][j] = 0
    su[i][j] = su[i-1][j]+su[i][j-1]-su[i-1][j-1]+dp[i][j]
    su[i][j] %= mod
    
print(su[n][m])

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
mod = 10**9+7
a = [0]+[int(i) for i in readline().split()]
b = [0]+[int(i) for i in readline().split()]
dp = [[0]*(m+1) for i in range(n+1)]
su = [[0]*(m+1) for i in range(n+1)]

dp[0][0] = 1
su[0][0] = 1
for i in range(1,n+1):
  su[i][0] = 1
for j in range(1,m+1):
  su[0][j] = 1
  
for i in range(1,n+1):
  for j in range(1,m+1):
    if a[i] == b[j]:
      dp[i][j] = su[i-1][j-1]
    else:
      dp[i][j] = 0
    su[i][j] = su[i-1][j]+su[i][j-1]-su[i-1][j-1]+dp[i][j]
    su[i][j] %= mod
    
print(su[n][m])
### BUGGY CODE ###

from collections import deque

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

q = deque()
s = 0

for i, j in enumerate(p):
    q.append((j+1)/2)
    if i == k-1:
        s = sum(q)
    elif i > k-1:
        q.popleft()
        s = max(s, sum(q))
print(s)

### FIXED CODE ###

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

s = 0
ans = 0

for i, j in enumerate(p):
    s+= (j+1)/2
    if i == k-1:
        ans = s
    if i > k-1:
        s -= (p[i-k]+1)/2
        ans = max(ans, s)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import ceil
def main():
    n, *a = map(int, read().split())
    #a2 = a[::-1]
    r = 0

    for i1 in range(1, n):
        if max(a[:i1]) > a[i1]:
            r += max(a[:i1]) - a[i1]
    print(r)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = map(int, read().split())
    r = 0
    st = a[0]
    for ae in a[1:]:
        if st > ae:
            r += st - ae
        else:
            st = ae
    print(r)


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

# 2020/02/09
# Educational DP Contest / DP まとめコンテスト - B

# Input
n, k = map(int,input().split())
h = list(map(int,input().split()))

dp = [10 ** 10] * n
dp[0] = 0

for i in range(1, n):
    j = max(0, i-k)
    while(j < i):
        acost = abs(h[i] - h[j]) + dp[j]
        if dp[i] > acost:
            dp[i] = acost
        j = j + 1

# Output
print(dp[n-1])

### FIXED CODE ###

# 2020/02/09
# Educational DP Contest / DP まとめコンテスト - B

# Input
n, k = map(int,input().split())
h = list(map(int,input().split()))

dp = [10 ** 10] * n
dp[0] = 0

for i in range(1, n):
    j = max(0, i-k)
    while(j < i):
        dp[i] = min(dp[i], abs(h[i] - h[j]) + dp[j])
        j = j + 1

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

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

B = [0] * Q
C = [0] * Q
for i in range(Q):
    B[i], C[i] = map(int, input().split())

for i in range(Q):
    for j in range(N):
        if A[j] == B[i]:
            A[j] = C[i]
    print(sum(A))

### FIXED CODE ###

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

t = [0] * 110000

for i in range(N):
    a = A[i]
    t[a] += 1

a = sum(A)

B = [0] * Q
C = [0] * Q
for i in range(Q):
    B[i], C[i] = map(int, input().split())

for i in range(Q):
    a = a + (C[i] - B[i]) * t[B[i]]
    t[C[i]] = t[C[i]] + t[B[i]]
    t[B[i]] = 0
    print(a)
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
def dfs(start, G):
    stack = [start]
    visited = [0]*len(G)
    while stack:
        label = stack.pop(0)
        visited[label-1]= 1
        for i in G[label-1]:
          if not visited[i-1]:
            #visited[label-1]= 1
            stack.append(i)
    return visited    
 
N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)
 
count = 0
visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    v_temp = dfs(i,G)
    visit = np.logical_or(visit, v_temp)
  else:
    visit[i-1] = 1
  count += 1
 
 
print(count)

### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**5+1)
input = sys.stdin.readline

def dfs(v,G,visit):
    visit[v-1]=1    
    for next in G[v-1]:        
        if visit[next-1]:
            continue
        _ = dfs(next,G,visit) 
 
N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)
 
count = 0

visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    _ = dfs(i,G,visit)
  else:
    visit[i-1] = 1
  count += 1

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

def main():
    N = int(input())
    result = 1
    for i in range(1, N + 1):
        result = result * i
    print(result % (10 ** 9 + 7))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    result = 1
    for i in range(1, N + 1):
        result = (result * i) % (10 ** 9 + 7)
    print(result)


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

import math

S = int(input())
Smod = [0]*2019
for i in range(int(math.log10(S)+2)):
  Smod[(S%(10**i))%2019] += 1

ans = 0
for j in range(2019):
  ans += Smod[j] * (Smod[j]-1) // 2
print(ans)

### FIXED CODE ###

S = input()
Sliststr = list(S)
Slist = [int(s) for s in Sliststr]
Smod = [0]
mod10 = [1]
count = [0]*2019
ans = 0
for i in range(len(S)-1):
  mod10.append(mod10[i]*10%2019)
for i in range(len(S)):
  Smod.append((Smod[i]+Slist[-i-1]*mod10[i])%2019)
for i in range(len(Smod)):
  count[Smod[i]] += 1
for i in range(2019):
  ans += count[i] * (count[i]-1) // 2
print(ans)
### BUGGY CODE ###

input()
a = map(int, input().split())
count = 0
while all(i%2 == 0 for i in a):
  a = [v//2 for v in a]
  count += 1
print(count)


### FIXED CODE ###

n = int(input())
a = map(int, input().split())
m = float('inf')
for i in a:
  count = 0
  while i%2 == 0:
    i = i//2
    count += 1
  m = min(m, count)
  if m==0:
    break
print(m)
### BUGGY CODE ###

n=input()

count=0
for j in range(1,int(n)+1):
    X=[]
    X=[int(x) for x in list(str(j))]
    if set(X)=={3,5,7}:
        count+=1
        
print(count)
    

### FIXED CODE ###

n=int(input())


L=[3,5,7]

def dfs(s):
    count=0
    for i in L:
        p=s*10+i
        if p<=n:
            if set([int(j) for j in str(p)])==set(L):
                count+=dfs(p)+1 #条件を満たしているので+1
            else:
                count+=dfs(p)
    return count

print(dfs(0))