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

S=input()
n=len(S)

c=0
for i in range(4,n+1):
    for j in range(n-i+1):
        if int(S[j:j+i])%2019==0:
            c+=1
print(c)

### FIXED CODE ###

s = input()
p = 2019
n = 0
ans = 0
mods = [0]*p
mods[0] = 1
for i, j in enumerate(reversed(s)):
  n += int(j)*pow(10, i, p)
  n %= p
  mods[n] += 1
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys
S = sys.stdin.readlines()

N,Q = map(int, S[0].split())
List = []
dic = {}
for i in S[1:N+1]:
    s, t, x = map(int, i.split())
    List.append([s-0.5-x, 1, x])
    List.append([t-0.5-x, -1, x])
    dic[x] = False
D = []
for i in S[N+1:]:
    D.append(int(i))

import heapq
    
List.sort()

h = []
j = 0
for i in range(Q):
    while j < 2*N and List[j][0] < D[i]:
        if List[j][1] == 1:
            heapq.heappush(h, List[j][2])
            dic[List[j][2]] = True
        else:
            dic[List[j][2]] = False
        j += 1
    while h:
        ans = h[0]
        if dic[ans]:
            print(ans)
            break
        else:
            heapq.heappop(h)
    if not h:
        print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N,Q = map(int, input().split())
List = []
dic = {}
for _ in range(N):
    s, t, x = map(int, input().split())
    List.append((s-0.5-x, 1, x))
    List.append((t-0.5-x, -1, x))
    dic[x] = False

import heapq
    
List.sort()

h = []
j = 0
for _ in range(Q):
    D = int(input())
    while j < 2*N and List[j][0] < D:
        if List[j][1] == 1:
            heapq.heappush(h, List[j][2])
            dic[List[j][2]] = True
        else:
            dic[List[j][2]] = False
        j += 1
    while h:
        ans = h[0]
        if dic[ans]:
            print(ans)
            break
        else:
            heapq.heappop(h)
    if not h:
        print(-1)
### BUGGY CODE ###

string = str(input())
     
pairs = 0
limit = len(string)-4
secondLimit = len(string)
substring = ''
for i in range(limit):
  substring += string[i]
  for j in range(i+1,secondLimit):
    substring += string[j]
    if j-i > 3 and int(substring) % 673 == 0:
      pairs += 1
  substring = ''
print(pairs)

### FIXED CODE ###

number = str(input())[::-1]
remainderDictionary = {0: 1}
    
sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum += int(i) * x
  sum %= 2019
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  ans += value * (value - 1) // 2 # N C 2
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
a = [int(x) for x in input().split()]
mod = 10**9+7
dp = [[0] * (K+1) for i in range(N+1)]
for i in range(K+1):
    dp[0][i] = 1
for i in range(1, N+1):
    for j in range(K+1):
        tmp = 0 if j-a[i-1]-1 < 0 else dp[i-1][j-a[i-1]-1]
        dp[i][j] += dp[i-1][j]-tmp
        dp[i][j] %= mod
    if i != N:
        for j in range(K):
            dp[i][j+1] = (dp[i][j+1]+dp[i][j])%mod
print(dp[N][K])

### FIXED CODE ###

N, K = map(int, input().split())
a = [int(x) for x in input().split()]
mod = 10**9+7
dp = [[0] * (K+1) for i in range(N+1)]
for i in range(K+1):
    dp[0][i] = 1
for i in range(1, N+1):
    for j in range(K+1):
        tmp = 0 if j-a[i-1]-1 < 0 else dp[i-1][j-a[i-1]-1]
        dp[i][j] += dp[i-1][j]-tmp
        dp[i][j] %= mod
    if i != N:
        for j in range(K):
            dp[i][j+1] = (dp[i][j+1]+dp[i][j])%mod
print(dp[N][K])
### BUGGY CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = INT()
A = LI()
mod = 10**9 + 7
ans = 0

for i in range(N):
    for j in range(i + 1, N):
        ans += A[i] * A[j]
        ans %= mod
        
print(ans)

### FIXED CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = INT()
A = LI()
mod = 10**9 + 7
sm = sum(A) - A[0]
ans = 0

for i in range(N - 1):
    ans += A[i] * sm
    ans %= mod
    sm -= A[i + 1]
    
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    pts = []
    m = 0
    while N != 0:
        x, y = map(int, input().split())
        for i in range(len(pts)):
            m = max(m, abs(pts[i][0] - x)+ abs(pts[i][1]-y))
        pts+= [[x,y]]
        N = N - 1
    print(m)

main()


### FIXED CODE ###

def main():
    N = int(input())
    x, y = map(int, input().split())
    a1 = x + y
    a2 = x + y
    b1 = y - x
    b2 = y - x
    N -= 1
    while N != 0:
        x, y = map(int, input().split())
        a1 = max(a1, x + y)
        a2 = min(a2, x + y)
        b1 = max(b1, y - x)
        b2 = min(b2, y - x)
        N = N - 1
    print(max(a1 - a2, b1 - b2))

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    limit = 10 ** 18

    ans = 1
    for i in a:
        ans *= i
    if ans > limit:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    limit = 10 ** 18

    if 0 in a:
        print(0)
        exit()

    ans = 1
    for i in a:
        ans *= i
        if ans > limit:
            ans = -1
            break

    print(ans)


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

# 解説
# ABC -> CBA
# BCは増えない&離れない
# AD -> DAを考える

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

S = input()
S = S.replace("BC", "D")
# print(S)

# ADからなる連続領域に分ける
ranges = []
i = 0
while i < len(S):
    while i < len(S) and S[i] != 'A' and S[i] != 'D':
        i += 1
    j = i
    while j < len(S) and (S[j] == 'A' or S[j] == 'D'):
        j += 1
    ranges.append((i, j - 1))
    i = j + 1

# 各AD列の点灯数を求める
total = 0
for (i, j) in ranges:
    # print(i, j, S[i:j+1])
    ans = 0
    for i in range(i, j + 1):
        for j in range(i + 1, j + 1):
            if S[i] == 'A' and S[j] == 'D':
                ans += 1
            # print(i, j, S[i], S[j])
    total += ans
print(total)



### FIXED CODE ###

# 解説
# ABC -> CBA
# BCは増えない&離れない
# AD -> DAを考える
# Aの右にBCが何個あるか

s = input()
n = len(s)
i = 0
ans = 0
count_a = 0

while i < n:
    if s[i] == 'A':
        count_a += 1
    elif i < n - 1 and s[i:i+2] == 'BC' and count_a > 0:
        ans += count_a
        i += 1
    else:
        count_a = 0
    i += 1
print(ans)
### BUGGY CODE ###

N=int(input())
dictionary={}
count=0
for i in range(N):
    s=str(sorted(input()))
    if s in dictionary:
        dictionary[s]+=1
        count+=dictionary[s]
    else:
        dictionary[s]=0
print(count)

### FIXED CODE ###

N=int(input())
dictionary={}
count=0
for i in range(N):
    s=tuple(sorted(input()))
    if s in dictionary:
        dictionary[s]+=1
        count+=dictionary[s]
    else:
        dictionary[s]=0
print(count)
### BUGGY CODE ###

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

a, b = [int(x) for x in input().split()]
s = set(range(a, b + 1))
for _ in range(M-1):
  a, b = [int(x) for x in input().split()]
  temp = set(range(a, b + 1))
  s = s & temp
print(len(s))

### FIXED CODE ###

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

max_a, min_b = 0, 10000000
for _ in range(M):
  a, b = [int(x) for x in input().split()]
  if a > max_a:
    max_a = a
  if b < min_b:
    min_b = b
if min_b < max_a:
  print(0)
else:
  print(min_b - max_a + 1)
### BUGGY CODE ###

n, k = map(int, input().split())
T = [[] for _ in range(n)]
E = []
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
  E.append((a, b))
d = k//2
def dfs(vs):
  dist = [-1]*n
  stack = []
  cnt = 0
  for v in vs:
    stack.append(v)
    dist[v] = 0
  while stack:
    v = stack.pop()
    for nv in T[v]:
      if dist[nv] == -1:
        dist[nv] = dist[v] + 1
        if dist[nv] > d:
          cnt += 1
        stack.append(nv)
  return cnt
ans = n
if k%2 == 0:
  for i in range(n):
    ans = min(ans, dfs([i]))
else:
  for l in E:
    ans = min(ans, dfs(l))
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
T = [[] for _ in range(n)]
E = []
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
  E.append((a, b))
d = k//2
def dfs(vs):
  dist = [-1]*n
  stack = []
  cnt = 0
  for v in vs:
    stack.append(v)
    dist[v] = 0
  while stack:
    v = stack.pop()
    for nv in T[v]:
      if dist[nv] == -1:
        dist[nv] = dist[v] + 1
        if dist[nv] > d:
          cnt += 1
        stack.append(nv)
  return cnt
ans = n
if k%2 == 0:
  for i in range(n):
    ans = min(ans, dfs([i]))
else:
  for l in E:
    ans = min(ans, dfs(l))
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())),reverse=True)
for i in range(k):
    if a==[]:
        break
    a.remove(a[0])
print(sum(a))

### FIXED CODE ###

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())),reverse=True)
if k>=len(a):
    print(0)
else:
    print(sum(a[k:]))
### BUGGY CODE ###

from collections import defaultdict

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

MOD = 10 ** 9 + 7

primes = defaultdict(int)

for a in A:
    x = a
    p = 2
    while p * p <= x:
        cnt = 0
        while x % p == 0:
            x //= p
            cnt += 1
        if cnt > 0:
            primes[p] = max(primes[p], cnt)
        p += 1
    if x > 1:
        primes[x] = max(primes[x], 1)

lcm = 1
for p in primes:
    lcm = (lcm * pow(p, primes[p], MOD)) % MOD

res = 0
for a in A:
    res = (res + (lcm * pow(a, MOD - 2, MOD) % MOD)) % MOD

print(res)


### FIXED CODE ###

from fractions import gcd
import sys

input = sys.stdin.readline

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

MOD = 10 ** 9 + 7


def lcm(a, b):
    return a * b // gcd(a, b)


l = A[0]
for a in A:
    l = lcm(l, a)

res = 0
for a in A:
    res = (res + (l * pow(a, MOD - 2, MOD)) % MOD) % MOD
    # res = (res + l // a) % MOD

print(res)
### BUGGY CODE ###

N = int(input())

for n in range(1, N+1):
    s = n//5
    cnt = 0
    flag = 0
    for x in range(1, s+1):
        for y in range(x, s+1):
            for z in range(y, s+1):
                f2 = 0
                siki = x**2 + y**2 + z**2 + x*y + y*z + z*x

                if siki == n:
                    # print('ans = ', siki)
                    if (x==y)and(y==z):
                        cnt += 1
                    elif (x!=y)and(y!=z):
                        cnt += 6
                    else:
                        cnt += 3
                # elif siki > n:
                    flag = 1
                    break
                elif siki > n:
                    f2 += 1
                    # print('x,y,z= ',x,y,z)
                    break

            if flag or f2==2:
                break
        if flag:
            break
    print(cnt)

### FIXED CODE ###

n=int(input())

ans=[0]*(n+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            f= x**2 + y**2 + z**2 + x*y + y*z + z*x
            if f<=n:
                ans[f]+=1

for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

import numba
from numba import jit

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [list(map(str, input().split())) for i in range(H)]
inf = float("inf")
dp = [[inf for i in range(W)] for i in range(H)]
dp[Ch-1][Cw-1] = 0
walk_move = [[-1, 0], [0, -1], [0, 1], [1, 0]]
magic_move = []
for a in range(-2, 3):
  for b in range(-2, 3):
    magic_move.append([a, b])

move_lis = [[Ch-1, Cw-1]]
already_lis = [[Ch-1, Cw-1]]

@jit
def main(move_lis, already_lis):
  while True:
    new_move_lis  = []
    for i,j in move_lis:
      if maze[i][0][j] == "#":
        continue
      for k,l in walk_move:
        if 0 <= i+k <= H-1 and 0 <= j+l <= W-1 and maze[i+k][0][j+l] == "." and not [i+k, j+l] in already_lis:
          dp[i+k][j+l] = min(dp[i+k][j+l], dp[i][j])
          new_move_lis.append([i+k, j+l])
          already_lis.append([i+k, j+l])
    if not len(new_move_lis):
      new_already_lis = []
      for o,p in already_lis:
        for m,n in magic_move:
          if not m and not n:
            continue
          if 0 <= o+m <= H-1 and 0 <= p+n <= W-1 and maze[o+m][0][p+n] == ".":
            dp[o+m][p+n] = min(dp[o+m][p+n], dp[o][p]+1)
            new_move_lis.append([o+m, p+n])
            new_already_lis.append([o+m, p+n])
      already_lis = new_already_lis
    if not len(new_move_lis) or dp[Dh-1][Dw-1] != inf:
      break
    else:
      move_lis = new_move_lis
  return dp[Dh-1][Dw-1]

ans = main(move_lis, already_lis)

if ans == inf:
  print("-1")
else:
  print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [input() for i in range(H)]

queue = deque()
queue.append((Ch-1, Cw-1, 0))
inf = float("inf")
table = [[inf] * W for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = ((-1, 0), (0, -1), (1, 0), (0, 1))
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.popleft()
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.appendleft((dx, dy, cost))
      table[dx][dy] = cost
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.append((dx, dy, cost+1))
      table[dx][dy] = cost+1

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])
### BUGGY CODE ###

N,M=map(int,input().split())
a=[[int(i) for i in input().split()] for l in range(M)]
l=[]
for x in a:
    if x[0]==1:l.append(x[1])
for x in a:
    if x[0] in l and x[1]==N:
        print("POSSIBLE")
        exit(0)
print("IMPOSSIBLE")

### FIXED CODE ###

N,M=map(int,input().split())
a=[[int(i) for i in input().split()] for l in range(M)]
l=[]
for x in a:
    if x[0]==1:l.append(x[1])
m=[]
for x in a:
    if x[1]==N:m.append(x[0])
if set(l) & set(m):
    print("POSSIBLE")
    exit(0)
print("IMPOSSIBLE")
### BUGGY CODE ###

from sys import maxint

N, K = map(int,raw_input().split())
stones = map(int,raw_input().split())

costs = [maxint] * N 
costs[0] = 0
for n in range(N) :
  for k in range(1,min(K, N-n-1)+1) : 
    costs[n+k] = min(costs[n+k], costs[n] + abs(stones[n]-stones[n+k]))
  
print costs[-1]

### FIXED CODE ###

from sys import maxint

N, K = map(int,raw_input().split())
stones = map(int,raw_input().split())

costs = [maxint] * N 
costs[0] = 0
for n in range(N) :
  for k in range(1,min(K, N-n-1)+1) : 
    costs[n+k] = min(costs[n+k], costs[n] + abs(stones[n]-stones[n+k]))
  
print costs[-1]
### BUGGY CODE ###

n,q=map(int, input().split())
s=input()
l=[list(map(int, input().split())) for i in range(q)]
for i in range(q):
    print(s[l[i][0]-1:l[i][1]].count("AC"))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
t=[0]*len(s)
for i in range(len(s)-1):
    if s[i]=="A" and s[i+1]=="C":
        t[i+1]=t[i]+1
    else:
        t[i+1]=t[i]+0
for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun May 31 17:19:32 2020

@author: NEC-PCuser
"""

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

if __name__ == "__main__":
    N = int(input())
    l = factorization(N)
    minimu = 10 ** 10
    ans = 0
    for i in range(0, 2**len(l)):
        a = 1
        b = 1
        for j in range(0, len(l)):
            if ((i >> j) & 1):
                a *= l[j]
            else:
                b *= l[j]
        if (abs(a - b) < minimu):
            minimu = abs(a - b)
            ans = max([len(str(a)), len(str(b))])
    print(ans)
            
                

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun May 31 17:19:32 2020

@author: NEC-PCuser
"""

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

def multiplication(n):
    ans = len(str(n))
    for i in range(2, int(-(-n**0.5//1))+1):
        if (n % i == 0):
            ans = max([len(str(i)), len(str(n // i))])
    return ans
        

if __name__ == "__main__":
    N = int(input())
    """
    l = factorization(N)
    """
    print(multiplication(N))
    """
    minimu = 10 ** 10
    ans = 0
    for i in range(0, 2**len(l)):
        a = 1
        b = 1
        for j in range(0, len(l)):
            if ((i >> j) & 1):
                a *= l[j]
            else:
                b *= l[j]
        if (abs(a - b) < minimu):
            minimu = abs(a - b)
            ans = max([len(str(a)), len(str(b))])
    print(ans)
    """
### BUGGY CODE ###

a = int(input())
ans = 1
flag = 0
for i in list(map(int,input().split())):
    ans *= i
    
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

a = int(input())
ans = 1
flag = 0
d = list(map(int,input().split()))
if 0 in d:
    print(0)
else:    
    for i in d:
        ans *= i 
        if ans > 10**18:
            flag = 1
            break
        else:
            continue
    if flag == 0:
        print(ans)
    else:
        print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-


def main():
    s = input()
    q = int(input())

    queries = [input().split() for i in range(q)]

    for query in queries:
        if "1" == query[0]:
            s = s[::-1]
        elif "2" == query[0]:
            if "1" == query[1]:
                s = query[2] + s
            elif "2" == query[1]:
                s += query[2]

    print(s)


if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    s = input()
    q = int(input())

    queries = (input().split() for i in range(q))

    flg = True
    result = s
    pre = ""
    post = ""
    for query in queries:
        if "1" == query[0]:
            flg = not flg
        elif "2" == query[0]:
            if ("1" == query[1] and flg) or ("2" == query[1] and not flg):
                pre = query[2] + pre
            else:
                post += query[2]

    if flg:
        print(pre + result + post)
    else:
        print((pre + result + post)[::-1])


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

def main():
  import numpy as np
  import itertools
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import dijkstra
  import sys
  readline = sys.stdin.readline
  readlines = sys.stdin.readlines

  N, M, R= map(int, readline().split())
  r = list(map(int,input().split()))
  lines = readlines()
  edge = np.array([line.split() for line in lines], dtype = np.int64).T
  #print(r)
  #print(edge)
  graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
  ans = float("inf")

  for town in itertools.permutations(r,R):
    #print(town)
    tmp = 0
    for i in range(R-1):
      distance_mat = dijkstra(graph, directed = False, indices = town[i]-1)
      tmp += distance_mat[town[i+1]-1]
    ans = min(ans,tmp)
  print(int(ans))
main()

### FIXED CODE ###

def main():
  import numpy as np
  import itertools
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import dijkstra
  import sys
  readline = sys.stdin.readline
  readlines = sys.stdin.readlines

  N, M, R= map(int, readline().split())
  r = list(map(int,input().split()))
  lines = readlines()
  edge = np.array([line.split() for line in lines], dtype = np.int64).T
  #print(r)
  #print(edge)
  graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
  ans = float("inf")
  distance_mat = {}
  for i in r:
    distance_mat[i-1] = (dijkstra(graph, directed = False, indices = i-1))

  for town in itertools.permutations(r,R):
    #print(town)
    tmp = 0
    for i in range(R-1):
      tmp += distance_mat[town[i]-1][town[i+1]-1]
    ans = min(ans,tmp)
  print(int(ans))
main()
### BUGGY CODE ###

import scipy.misc as scm
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
n = int(input())
a = list(map(int,input().split()))
p=10**9+7
ans=0
X=[1]  #階乗テーブル
for i in range(1,n+1):
  X+=[ (X[-1]*i) %p ]
Y=[1]*(n+1)  #階乗の逆元テーブル
Y[n]=power_func(X[n],p-2,p)
for i in range(n-1,-1,-1):
  Y[i]=Y[i+1]*(i+1) %p

#ダブりをみつける
check = [0]*n
for i in range(n+1):
  if check[a[i]-1]==1: dub = a[i]
  else: check[a[i]-1] = 1

indexes = [i for i, x in enumerate(a) if x == dub]
ind1, ind2  = indexes[0], indexes[1]

for i in range(1,n+2):
  ans = scm.comb(n+1, i, 1)
  if ind1 + n -ind2 +1 >= i:
    for j in range(i):
      ans -= scm.comb(ind1, j, 1)* scm.comb(n-ind2,i-j-1,1)
  print(ans%p)

### FIXED CODE ###

def comb(k,r):
  """kCpを求める"""
  if k<0 or r<0 or r>k: return 0
  elif k==0 or r==0: return 1
  else:
    return (X[k]*Y[r]*Y[k-r])
  
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
n = int(input())
a = list(map(int,input().split()))
p=10**9+7
ans=0
X=[1]  #階乗テーブル
for i in range(1,n+2):
  X+=[ (X[-1]*i) %p ]
Y=[1]*(n+2)  #階乗の逆元テーブル
Y[n+1]=power_func(X[n+1],p-2,p)
for i in range(n,-1,-1):
  Y[i]=Y[i+1]*(i+1) %p

#ダブりをみつける
check = [0]*n
for i in range(n+1):
  if check[a[i]-1]==1: dub = a[i]
  else: check[a[i]-1] = 1

indexes = [i for i, x in enumerate(a) if x == dub]
ind1, ind2  = indexes[0], indexes[1]

for i in range(1,n+2):
  ans = comb(n+1, i)
  if ind1 + n -ind2 +1 >= i:
    ans -= comb(ind1 + n -ind2, i-1)
  print(ans%p)
### BUGGY CODE ###

def sort_str(str):
  return ''.join(sorted(list(str)))

n = int(input().rstrip())
s = [sort_str(input().rstrip()) for _ in range(n)]

ans = 0
pool = {}
for i in range(n):
  if not s[i] in pool.keys():
    pool[s[i]] = 0
  else:
    pool[s[i]] += 1
    ans += pool[s[i]]
print(ans)

### FIXED CODE ###

def sort_str(str):
  return ''.join(sorted(list(str)))

n = int(input().rstrip())
s = [sort_str(input().rstrip()) for _ in range(n)]

ans = 0
pool = {}
for i in range(n):
  if not s[i] in pool.keys():
    pool[s[i]] = 0
  else:
    pool[s[i]] += 1
    ans += pool[s[i]]
print(ans)
### BUGGY CODE ###

# coding: utf-8
N, Q = map(int, input().split())
S = input()
c = 0
lst = [0] * N
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        c += 1
        lst[i + 1] = c
for _ in range(Q):
    a, b = map(int, input().split())
    c = max(lst[a - 1:b])
    d = max(lst[:a])
    print(max(c - d, 0))

### FIXED CODE ###

# coding: utf-8
N, Q = map(int, input().split())
S = input()
c = 0
lst = [0] * N
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        c += 1
    lst[i + 1] = c
for _ in range(Q):
    a, b = map(int, input().split())
    print(lst[b - 1] - lst[a - 1])
### BUGGY CODE ###

n=int(input())
l=[]
ans=0
for i in range(n):
  s=str(input())
  if s not in l:
    l.append(s)
    ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
l=[]
for i in range(n):
  s=str(input())
  l.append(s)
print(len(set(l)))