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

import math

a,b = map(int,input().split())

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

if min(a,b) == 1:
    print(1)
    exit()

ans = 1
tmp = 1
for i in range(2,(max(a,b)+1)):
    if a%i == 0 and b%i == 0:
        l = factorization(i)
        for j in range(len(l)):
            if tmp%l[j][0] == 0:
                break
            else:
                tmp *= l[j][0]
        else:
            ans += 1

print(ans)



### FIXED CODE ###

a,b = map(int,input().split())

if min(a,b) == 1:
    print(1)
    exit()

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

A = factorization(a)
B = factorization(b)
ans = len(set(A) & set(B))
print(ans+1)
### BUGGY CODE ###

n, k, l = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(k)]
R = [[int(i) for i in input().split()] for j in range(l)]

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    for e in self.elements:
      self._root[e] = e
    
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if not x == y:
      self._root[x] = y
    
  def root(self, x):
    if not self._root[x] == x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]
  
  def count(self):
    cnt = {}
    for e in self.elements:
      cnt[self.root(e)] += cnt.get(self.root(e), 0)
      
    for e in self.elements:
      yield cnt.get(e, 0)
      
  def get_union(self):
    union = {}
    for e in self.elements:
      if self.root(e) in union:
        union[self.root(e)].add(e)
      else:
        union[self.root(e)] = {e}
    return union
      
  
road = UnionFind(range(1, n+1))
rail = UnionFind(range(1, n+1))

for i in range(k):
  road.unite(P[i][0], P[i][1])
  
for i in range(l):
  rail.unite(R[i][0], R[i][1])

ans = {}
for e in range(1, n+1):
  key = (road.root(e), rail.root(e))
  ans[key] = ans.get(key, 0) +1
  
for e in range(1, n+1):
  print(ans[(road.root(e), rail.root(e))], end=' ')

### FIXED CODE ###

n, k, l = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(k)]
R = [[int(i) for i in input().split()] for j in range(l)]

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    for e in self.elements:
      self._root[e] = e
    
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if not x == y:
      self._root[x] = y
    
  def root(self, x):
    if not self._root[x] == x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]
  
  def count(self):
    cnt = {}
    for e in self.elements:
      cnt[self.root(e)] += cnt.get(self.root(e), 0)
      
    for e in self.elements:
      yield cnt.get(e, 0)
      
  def get_union(self):
    union = {}
    for e in self.elements:
      if self.root(e) in union:
        union[self.root(e)].add(e)
      else:
        union[self.root(e)] = {e}
    return union
      
  
road = UnionFind(range(1, n+1))
rail = UnionFind(range(1, n+1))

for i in range(k):
  road.unite(P[i][0], P[i][1])
  
for i in range(l):
  rail.unite(R[i][0], R[i][1])

ans = {}
key = []
for e in range(1, n+1):
  key.append((road.root(e), rail.root(e)))
  ans[key[-1]] = ans.get(key[-1], 0) +1
  
for k in key:
  print(ans[k], end=' ')
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for j in range(n):
        if s[j] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for j in range(n):
        if s[j] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

N, X = map(int, input().split())
x = list(map(int, input().split()))
d = []

for item in x:
  d.append(abs(X- item))

m = min(d)
ans = 0
flag = 0

for i in range(m, 1, -1):
  flag = 1
  for j in range(N):
    if(d[j] % i != 0):
      flag = 0
      break
  if(flag == 1):
    ans = i
    break
  
if(flag == 0):
  print(1)
  
else:
  print(ans)

### FIXED CODE ###

def gcd(a, b):
  if(a == b):
    return a
  elif(a % b == 0):
    return b
  elif(b % a == 0):
    return a
  elif(a == 1 or b == 1):
    return 1
  elif(a > b):
    return gcd(a- a// b* b, b)
  elif(a < b):
    return gcd(a, b- b// a* a)

def ggcd(lista):
  if(len(lista) == 1):
    return lista.pop()
  else:
    l = lista.pop()
    for i in range(1, len(lista)):
      l = gcd(l, lista.pop())
    return l

N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
d = []
gcds = set()
x.sort()

for i in range(N):
  d.append(x[i+ 1]- x[i])

gcds.add(d[0])

for i in range(N- 1):
  if(d[i+ 1] != d[i]):
    gcds.add(d[i+ 1])

print(ggcd(gcds))
### BUGGY CODE ###

# ABC127C - Prison
n, m = list(map(int, input().rstrip().split()))
a, b = list(map(int, input().rstrip().split()))
ans = {i for i in range(a, b + 1)}
for _ in range(m - 1):
    a, b = list(map(int, input().rstrip().split()))
    ans = ans & {i for i in range(a, b + 1)}
print(len(ans))

### FIXED CODE ###

# ABC127C - Prison
n, m = list(map(int, input().rstrip().split()))
lst = [list(map(int, input().rstrip().split())) for _ in range(m)]
ans = 0
l, r = lst[0][0], lst[0][1]
for i in lst[1:]:
    l = max(l, i[0])
    r = min(r, i[1])
for i in range(1, n + 1):
    if l <= i <= r:
        ans += 1
print(ans)
### BUGGY CODE ###

s = input()
l = len(s)
for i in range(l):
  for j in range(l-1,i,-1):
    if s[i]=="A" and s[j]=="Z":
      print(j-i+1)
      exit()
      
      

### FIXED CODE ###

s = input()
 
for i in range(len(s)):
    if s[i] == 'A':
        a = i
        break
for i in range(-1,-len(s),-1):
    if s[i] == 'Z':
        b = len(s) + i
        break
 
print(b-a+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [[0 for _ in range(h+1)] for _ in range(h+1)]
    dp = [[0 for _ in range(h+1)] for _ in range(h+1)]
    for j in range(W-1):
        for x in range(h+1):
            for y in range(h+1):
                w[x][y] = 0
                if x == 0 and y == 0:
                    for z in range(h):
                        if c[z][j] == c[z][j+1]:
                            w[x][y] += 1
                    dp[x][y] = 0
                    continue
                if x == 0:
                    for z in range(h-y):
                        if c[y+z][j] == c[z][j+1]:
                            w[x][y] += 1
                    dp[x][y] = dp[x][y-1]+w[x][y-1]
                    continue
                if y == 0:
                    for z in range(h-x):
                        if c[z][j] == c[x+z][j+1]:
                            w[x][y] += 1
                    dp[x][y] = dp[x-1][y]+w[x-1][y]
                    continue
                w[x][y] = w[x-1][y-1]
                if c[h-x][j] == c[h-y][j+1]:
                    w[x][y] -= 1
                dp[x][y] = min(dp[x][y-1]+w[x][y-1],dp[x-1][y]+w[x-1][y])
        ans += dp[h][h]
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [0 for _ in range((h+1)**2)]
    dp = [0 for _ in range((h+1)**2)]
    for j in range(W-1):
        for x in range(h,0,-1):
            for y in range(h,0,-1):
                w[(x-1)*(h+1)+y-1] = w[x*(h+1)+y]
                if c[h-x][j] == c[h-y][j+1]:
                    w[(x-1)*(h+1)+y-1] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    if x == y:
                        dp[x*h+y] = 0
                    elif x == 0:
                        dp[x*(h+1)+y] = dp[x*(h+1)+y-1]+w[x*(h+1)+y-1]
                    else:
                        dp[x*(h+1)+y] = dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y]
                    continue
                dp[x*(h+1)+y] = min(dp[x*(h+1)+y-1]+w[x*(h+1)+y-1],dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y])
        ans += dp[-1]
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

gate=[i for i in range(N)]
l,r=map(int,input().split())
ans=gate[l-1:r]

for i in range(M-1):
  l,r=map(int,input().split())
  new_ans=gate[l-1:r]
  ans=list(set(ans)&set(new_ans))
print(len(ans))

### FIXED CODE ###

N,M=map(int,input().split())
L,R=[],[]

for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
L.sort(reverse=True)
R.sort()

if R[0]>=L[0]:
  print(R[0]-L[0]+1)
else:
  print(0)
### BUGGY CODE ###

H, W, M = map(int, input().split())
hallline = [0 for i in range(H)]
wallline = [0 for i in range(W)]
for j in range(W):
    wallline[j] = 0
b = [[False for i in range(W)] for j in range(H)]

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b[tmp[0]][tmp[1]] = True

t = max(hallline)
s = max(wallline)

hkeys = [i for i in range(H) if hallline[i] == t]
wkeys = [i for i in range(W) if wallline[i] == s]

for i in hkeys:
    for j in wkeys:
        if not b[i][j]:
            print(t + s)
            exit()
print(t + s - 1)


### FIXED CODE ###

H, W, M = map(int, input().split())
hallline = [0 for i in range(H)]
wallline = [0 for i in range(W)]
b = {}

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b[(tmp[0], tmp[1])] = True

t = max(hallline)
s = max(wallline)

a = [i for i in range(H) if hallline[i] == t]
c = [i for i in range(W) if wallline[i] == s]

tmp = False

for i in a:
    for j in c:
        if (i, j) not in b.keys():
            print(t + s)
            tmp = True
            break
    if tmp:
        break
if not tmp:
    print(t + s - 1)
### BUGGY CODE ###

import sys

n = int(input())
strs = [input() for i in range(n)]

ret = []
for str in strs:
  l = list(str)
  s = sorted(l)
  ret.append("".join(s))

set = set(ret)

count = 0
for index, content in enumerate(ret):
  if index < len(ret) - 1:
    list = ret[index+1:]
    count += list.count(content)
print(count)

### FIXED CODE ###

import sys

n = int(input())
originals = [input() for i in range(n)]

ret = {}
count = 0
for original in originals:
  str = "".join(sorted(list(original)))
  if str in ret:
    count += ret[str]
    ret[str] += 1
  else:
    ret[str] = 1
print(count)
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

# l = [(i,childs_list[i],0)]
l = [(i,childs_list[i],0) for i in roots]
costs = [ 0 for _ in range(N)]

while l: 
    nex_stack = []

    for p in l:
        v_idx, chlist, cnt = p
        costs[v_idx] = max(costs[v_idx], cnt)

        for c in chlist:
            if cnt+1 > costs[c]:
                # l.append(  (c, childs_list[c], cnt+1) ) 
                nex_stack.append( (c, childs_list[c], cnt+1) ) 

    l = nex_stack
print(max(costs))
        
        



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

l = [ i for i in roots]
costs = [ 0 for _ in range(N)]

while l: 

    nex_stack = []
    # p = l.pop()
    for p in l:
        # cnt = costs[p]
        for c in childs_list[p]:
            costs[c] = max(costs[p]+1, costs[c])
            childs[c] -= 1
            if childs[c] == 0:
                nex_stack.append(c)
    
    l = nex_stack


print(max(costs))
### BUGGY CODE ###

N, K, L = map(int, input().split())
links1 = [tuple(map(int, input().split())) for _ in range(K)]
links2 = [tuple(map(int, input().split())) for _ in range(L)]

linked1 = {i: set([i]) for i in range(1, N + 1)}
linked2 = {i: set([i]) for i in range(1, N + 1)}

for p, q in links1:
    set1 = linked1[p]
    set2 = linked1[q]
    set1 |= set2
    for i in set2:
        linked1[i] = set1

for r, s in links2:
    set1 = linked2[r]
    set2 = linked2[s]
    set1 |= set2
    for i in set2:
        linked2[i] = set1

counts = []
for n in range(1, N + 1):
    set1 = linked1[n]
    set2 = linked2[n]
    counts.append(str(len(set1.intersection(set2))))

print(' '.join(counts))

### FIXED CODE ###

from collections import Counter


class UnionFind:

    def __init__(self, n: int) -> None:
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, i: int) -> None:
        if self.parent[i] == i:
            return i
        else:
            return self.find(self.parent[i])

    def unite(self, i: int, j: int) -> None:
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i == root_j:
            return
        if self.rank[root_i] < self.rank[root_j]:
            self.parent[root_i] = root_j
        else:
            self.parent[root_j] = root_i
            if self.rank[root_i] == self.rank[root_j]:
                self.rank[root_i] += 1

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

uf1 = UnionFind(N)
for _ in range(K):
    i, j = map(int, input().split())
    uf1.unite(i - 1, j - 1)

uf2 = UnionFind(N)
for _ in range(L):
    i, j = map(int, input().split())
    uf2.unite(i - 1, j - 1)

set_id_pairs = [(uf1.find(i), uf2.find(i)) for i in range(N)]
counter = Counter(set_id_pairs)
counts = [counter[set_id_pairs[i]] for i in range(N)]
print(' '.join(str(c) for c in counts))
### BUGGY CODE ###

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

diff = 2020202020 * 200000 + 1

tot = sum(A)

for i in range(N):
    temp1 = A[:i+1]
    # temp2 = A[i+1:]
    temp3 = abs(tot - 2 * sum(temp1))
    if temp3 <= diff:
        # mid = i
        diff = temp3

print(diff)


### FIXED CODE ###

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


diff = 2020202020 * 200000 + 1
tot = sum(A)

temp1 = 0

for i in range(N):
    temp1 += A[i]
    # temp2 = A[i+1:]
    temp3 = abs(tot - 2 * temp1)
    if temp3 <= diff:
        # mid = i
        diff = temp3
    else:
        break

print(diff)
### BUGGY CODE ###

import collections
import math

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

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def primelist(n):
    P = [2]
    flag = 0
    for i in range(3,n+1,2):
        for j in range(len(P)):
            if math.sqrt(i) < P[j]:
                break
            else:
                if i%P[j] == 0:
                    flag += 1
                    break
        if flag == 0:
            P.append(i)
        flag = 0
    P.append(1)
    return(P)

def yakusuu(A):
    Y=[]
    for i in range(1,A+1):
        if N%i==0:
            Y.append(i)
    return(Y)


N=gcd(A,B)

if N==1:
    print(1)
else:
    c = collections.Counter(prime_factorize(N))
    ms = list(c.keys())[-1]
    pl = primelist(N)
    ya = yakusuu(N)
    
    #print(N,ms,pl,ya)
    
    count=0
    for i in range(len(pl)):
        if pl[i] in ya:
            count+=1
    print(count)

### FIXED CODE ###

import collections

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A,B=map(int, input().split())
N=gcd(A,B)
c = collections.Counter(prime_factorize(N))
print(len(list(c.keys()))+1)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = deque([])
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 0

while len(ls) > 0:
    h, w = ls.popleft()

    if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
        dp[h+1][w] = dp[h][w] + 1
        ls.append([h+1,w])
    if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
        dp[h-1][w] = dp[h][w] + 1
        ls.append([h-1,w])
    if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
        dp[h][w+1] = dp[h][w] + 1
        ls.append([h,w+1])
    if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
        dp[h][w-1] = dp[h][w] + 1
        ls.append([h,w-1])

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dp[i][j])

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 1

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = 1
            temp.append([h,w-1])
    ls = temp

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

n,m,s,t = map(int, input().split())
L = [[int(x) for x in input().split()] for _ in range(m)]

cost = [[[10**15, 10**15] for _ in range(n)] for _ in range(n)]
for i in range(m):
    cost[L[i][0]-1][L[i][1]-1] = L[i][2:]
    cost[L[i][1]-1][L[i][0]-1] = L[i][2:]
    
for i in range(n):
    cost[i][i] = [0, 0]
    
def dijkstra(s, n, cost, c):
    d = [10**15]*n
    used = [0]*n
    d[s] = 0
    while True:
        v = -1
        for i in range(n):
            if used[i] == 0 and v == -1:
                v = i
            elif used[i] == 0 and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = 1
        
        for j in range(n):
            d[j] = min(d[j], d[v]+cost[v][j][c])
    return d

jpy = dijkstra(s-1, n, cost, 0)
snook = dijkstra(t-1, n, cost, 1)
ans_list = [10**15]*n
ans_list[n-1] = jpy[n-1]+snook[n-1]
for i in range(n-2, -1, -1):
    ans_list[i] = min(ans_list[i+1], jpy[i]+snook[i])
    
for i in range(n):
    print(10**15-ans_list[i])

### FIXED CODE ###

import heapq

n,m,s,t = map(int, input().split())
L = [[int(x) for x in input().split()] for _ in range(m)]

cost = [[] for _ in range(n)]
for i in range(m):
    cost[L[i][0]-1].append((L[i][2], L[i][3], L[i][1]-1))
    cost[L[i][1]-1].append((L[i][2], L[i][3], L[i][0]-1))
    
def dijkstra(s, n, cost, c):
    g = 10**6
    d = [10**15]*n
    used = [0]*n
    d[s] = 0
    used[s] = 1
    edgelist = []
    for e in cost[s]:
        heapq.heappush(edgelist, e[c]*g+e[2])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge%g] == 1:
            continue
        v = minedge%g
        d[v] = minedge//g
        used[v] = 1
        for e in cost[v]:
            if used[e[2]] == 0:
                heapq.heappush(edgelist, (e[c]+d[v])*g + e[2])
    return d

jpy = dijkstra(s-1, n, cost, 0)
snuuk = dijkstra(t-1, n, cost, 1)
ans_list = [0]*n
ans_list[n-1] = jpy[n-1]+snuuk[n-1]
for i in range(n-2, -1, -1):
    ans_list[i] = min(ans_list[i+1], jpy[i]+snuuk[i])
    
for i in range(n):
    print(10**15-ans_list[i])
### BUGGY CODE ###

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

a = [int(input()) for _ in range(M)]

dp = [0] * (N + 1)

dp[0] = 1

if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, N + 1):
    if i in a:
        continue
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= 1000000007

print(dp[-1])




### FIXED CODE ###

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

# a = [int(input()) for _ in range(M)]
a = set([int(input()) for _ in range(M)])

dp = [0] * (N + 1)
dp[0] = 1

if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, N + 1):
    if i in a:
        continue
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= 1000000007

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

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    S = [s for s in sr()]
    N = len(S)
    a = defaultdict(int)
    a[0] += 1
    t = ''
    for i in range(N):
        t = S.pop()+t
        a[int(t)%2019] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    S = sr()
    N = len(S)
    a = [0]*2019
    a[0] += 1
    t = 0
    r = 1
    for s in reversed(S):
        t += int(s)*r
        t %= 2019
        r *= 10
        r %= 2019
        a[t] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()
### BUGGY CODE ###

n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
con=[[] for i in range(n+1)]
check=[0 for i in range(n+1)]
for x in lst: con[x[0]].append(x[1]);con[x[1]].append(x[0])
check[1]=1
work=[1]
while check.count(0)>1:
    workc=[]
    for x in work:
        for y in con[x]:
            if check[y] : continue
            else : 
                workc.append(y)
                check[y]=x
    work=workc
print("Yes")
for j in range(2,n+1):
    print(check[j])

### FIXED CODE ###

n,m=map(int,input().split())
graph=[[] for _ in range(n)]

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

sign=[-1]*n
sign[0]=0
work=[]
work_next=graph[0]
for x in work_next:
    sign[x]=0


while work_next:
    work=work_next[:]
    work_next=[]
    for x in work:
        for y in graph[x]:
            if sign[y]>=0 : continue
            if y in work_next : continue
            sign[y]=x
            work_next.append(y)

if -1 in sign : print("No");exit()
print("Yes")
for i in range(1,n):
    print(sign[i]+1)
### BUGGY CODE ###

import numpy as np
s = input()
print(0) if int(s) < 2019 else print(sum(np.mod(int(s[j:i+j]), 2019) == 0 for i in range(4, len(s)) for j in range(len(s)-i+1)))

### FIXED CODE ###

import numpy as np

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = ans[np.nonzero(ans)]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(ans_c.shape[0])]) / 2) + ans[0])