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

from sys import stdin
import itertools
def main():
    number = int(input())
    num_list = list(map(int, stdin.readline().split()))
    comb = list(itertools.combinations(num_list, 2))
    total = sum([c1*c2 for c1, c2 in comb])
    print(total % (10**9 + 7))
if __name__ == '__main__':
    main()

### FIXED CODE ###

from sys import stdin
import itertools
def main():
    number = int(input())
    num_list = list(map(int, stdin.readline().split()))
    num_list_sum = sum(num_list)
    total = 0
    for i in range(number):
        num_list_sum -= num_list[i]
        total += num_list[i] * num_list_sum
    print(total % (10**9+7))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
lr_lists = []
for i in range(Q):
    lr = list(map(int,input().split()))
    lr_lists.append(lr)

for i in range(Q):
    start = lr_lists[i][0] -1
    end = lr_lists[i][1] 
    str_list = S[start:end]

    count = 0
    for j in range(0,len(str_list)-1):
        if str_list[j] == "A" and str_list[j+1] == "C":
            count += 1
    print(count)

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()

count_list = [0]*(N+1)

for i in range(N):
    if S[i:i+2] == 'AC':
        count_list[i+1] = count_list[i] + 1
    else:
        count_list[i+1] = count_list[i]

for i in range(Q):
    l, r = map(int,input().split())
    print(count_list[r-1] - count_list[l-1])
### BUGGY CODE ###

K = int(input())
ans = 0
ans1 = -1
if K%2 == 0:
  print(-1)
else:
  for i in range(30000):
    ans += 7*10**i
    if ans%K == 0:
      ans1 = i+1
      break
if ans1 == -1 and K%2 ==1:
  print(K-1)
elif K%2 == 1:
  print(ans1)

### FIXED CODE ###

K = int(input())
if K%7 == 0:
  L = 9*K//7
else:
  L = 9*K

if K%2 == 0 or K%5 == 0:
  print(-1)
else:
  X = 10%L
  if X == 1:
    print(1)
  else:
    for i in range(K):
      X = X*10 % L
      if X == 1:
        print(i+2)
        break
### BUGGY CODE ###

n,m,r=map(int, input().split())
s=[[100000]*n for i in range(n)]
t=list(map(int, input().split()))
for i in range(m):
    a,b,c=map(int, input().split())
    s[a-1][b-1]=c
    s[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            s[i][j]=min(s[i][j],s[i][k]+s[k][j])
ans=0
for i in range(r-1):
    for j in range(i+1,r):
        ans=max(s[t[i]-1][t[j]-1],ans)
print(ans)

### FIXED CODE ###

n,m,r=map(int, input().split())
s=[[10**9]*n for i in range(n)]
t=list(map(int, input().split()))
for i in range(m):
    a,b,c=map(int, input().split())
    s[a-1][b-1]=c
    s[b-1][a-1]=c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            s[i][j]=min(s[i][j],s[i][k]+s[k][j])
ans=float('inf')
from itertools import permutations
for i in permutations(t):
    an=0
    for j in range(r-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(ans)
### BUGGY CODE ###

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

works = []
for _ in range(N):
    A, B = map(int, input().split())
    works.append((A, B))

works = sorted(works, key=lambda x: -x[1])

total = 0
for m in range(1, M+1):
    for i in range(len(works)):
        if works[i][0] <= m:
            total += works.pop(i)[1]
            break

print(total)

### FIXED CODE ###

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

jobs = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int, input().split())
    if A > M:
        continue
    jobs[A-1].append(-B)

total = 0
heap = []
for i in range(M):
    for job in jobs[i]:
        heapq.heappush(heap, job)

    if len(heap) == 0:
        continue
    else:
        total += -heapq.heappop(heap)

print(total)
### BUGGY CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    adj[u-1].append(v-1)
S, T = map(int, input().split())
    
#connect nodes which are 3 steps distant.
start = []
goal = []
for n0 in range(N):
    nodes_1_step  = set(adj[n0])
    nodes_2_steps = set()
    for n1 in nodes_1_step:
        nodes_2_steps |= set(adj[n1])
    nodes_3_steps = set()
    for n2 in nodes_2_steps:
        nodes_3_steps |= set(adj[n2])

    start += [n0] * len(nodes_3_steps)
    goal += list(nodes_3_steps)

cost = [1] * len(start)
digraph = csr_matrix((cost, (start, goal)), (N, N))

ans = dijkstra(digraph, unweighted = True, indices = S-1)[T-1]
    
if ans == float("inf"):
    print(-1)
else:
    print(int(ans))

### FIXED CODE ###

from collections import deque

#create digraph
#nodes will be (steps % 3) * N + node
N, M = map(int, input().split())
adj = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    adj[      u].append(  N + v)
    adj[  N + u].append(2*N + v)
    adj[2*N + u].append(      v)

S, T = map(int, input().split())
S -= 1
T -= 1

#bfs
q = deque([S])
depth = [10 ** 9] * (3*N)
depth[S] = 0
while q:
    node = q.popleft()
    if node == T:
        break
    for next_node in adj[node]:
        if depth[next_node] > depth[node] + 1:
            depth[next_node] = depth[node] + 1
            q.append(next_node)

if depth[T] == 10 ** 9:
    print(-1)
else:
    print(depth[T] // 3)
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())
    S = input()
    RGB = ('R', 'G', 'B')
    Cumsum = [[0] * 3 for i in range(N + 1)]
    for i in range(N):
        Cumsum[i + 1][0] = Cumsum[i][0] + (1 if S[i] == 'R' else 0)
        Cumsum[i + 1][1] = Cumsum[i][1] + (1 if S[i] == 'G' else 0)
        Cumsum[i + 1][2] = Cumsum[i][2] + (1 if S[i] == 'B' else 0)

    ans = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            if S[i] != S[j]:
                cnt = Cumsum[N][3 - RGB.index(S[i]) - RGB.index(S[j])] - Cumsum[j][3 - RGB.index(S[i]) - RGB.index(S[j])]
                if 2 * j - i < N:
                    if S[2 * j - i] == RGB[3 - RGB.index(S[i]) - RGB.index(S[j])]:
                        cnt -= 1
                ans += cnt
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import collections


def main():
    N = int(input())
    S = input()
    RGB = ('R', 'G', 'B')
    cnt = collections.Counter(S)
    ans = cnt['R'] * cnt['G'] * cnt['B']

    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            if S[i] != S[j]:
                if 2 * j - i < N:
                    if S[2 * j - i] == RGB[3 - RGB.index(S[i]) - RGB.index(S[j])]:
                        ans -= 1

    print(ans)


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

k, s = map(int, input().rstrip("\n").split())
print(sum([x + y + z == s for x in range(k + 1) for y in range(k + 1) for z in range(k + 1)]))


### FIXED CODE ###

k, s = map(int, input().rstrip("\n").split())
count = 0

for x in range(k + 1):
    for y in range(k + 1):
        if x + y > s:
            x = k + 1
            y = k + 1
            continue
        count += (s <= x + y + k)

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

n = int(input())
list = []
ans = 0
for i in range(n):
  list.append(input())
  list[i] = ''.join(sorted(list[i]))
for i in range(n):
  for j in range(i+1,n):
    if list[i] == list[j]:
      ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
dict= {}
ans = 0
for i in range(n):
  temp = ''.join(sorted(input()))
  if temp in dict:
    dict[temp] += 1
    ans += dict[temp]
  else:
    dict.update([(temp, 0)])
print(ans)
### BUGGY CODE ###

from collections import Counter
N, M = map(int, input().split())
A = list(map(int, input().split()))

A = Counter(A)

for _ in range(M):
    b, c = map(int, input().split())
    A[c] += b

A = list(A.elements())
A.sort(reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

from collections import Counter
n, m = map(int, input().split())
a = Counter(list(map(int, input().split())))

for i in range(m):
    b, c = map(int, input().split())
    a[c] += b

num = sorted(a.items(), key=lambda x: x[0], reverse=True)
ans = 0

for key, val in num:
    if n > val:
        ans += key * val
        n -= val
    else:
        ans += key * n
        break

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

from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
N,M,K=map(int,input().split())
uf=UnionFind(N+1)
A = [set() for _ in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  uf.unite(a,b)
  A[a].add(b)
  A[b].add(a)
  
B = [set() for _ in range(N+1)]
for i in range(K):
  c,d=map(int,input().split())
  B[c].add(d)
  B[d].add(c)
  
groups=defaultdict(set)
for i in range(1,N+1):
  g = uf.find(i)
  if g>0:
    groups[g].add(i)
    
ans = [len(groups[uf.find(i)].difference(A[i]).difference(B[i]))-1 for i in range(1,N+1)]

print(*ans)

### FIXED CODE ###

from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
N,M,K=map(int,input().split())
uf=UnionFind(N+1)
n_friends=defaultdict(int)
for i in range(M):
  a,b=map(int,input().split())
  uf.unite(a,b)
  n_friends[a] += 1
  n_friends[b] += 1
  
ans = [uf.size(i)-n_friends[i]-1 for i in range(N+1)]

for i in range(K):
  c,d=map(int,input().split())
  if uf.same(c,d):
    ans[c] -= 1
    ans[d] -= 1
  
print(*ans[1:])
### BUGGY CODE ###

# 2019/08/16

from collections import Counter

s=list(input())
t=list(input())

c1={}
c2={}
for ss,tt in zip(s,t):
    c1[ss]=c1.get(ss,'')+tt
    c2[tt]=c2.get(tt,'')+ss
    if len(set(c1[ss]))>1 or len(set(c2[tt]))>1:
        print('No')
        exit()

print('Yes')

### FIXED CODE ###

# 2019/08/16

s=list(input())
t=list(input())

c1={}
c2={}
for ss,tt in zip(s,t):
    if c1.get(ss) is None:
        c1[ss]=tt
    if c2.get(tt) is None:
        c2[tt]=ss
    if c1[ss]==tt and c2[tt]==ss:continue
    else:
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [list(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    flag = [True]*N
    min_id = 0
    while(min_id < N-1):
        ans += 1
        if ans > (N*(N-1)) // 2:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    if Lock[A[i][id[i]]-1] == i and i not in tmp:
                        Lock[A[i][id[i]]-1] = -1
                        id[A[i][id[i]]-1] += 1
                        tmp.add(A[i][id[i]]-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > (N*(N-1)) // 2:
        print(-1)
    else:
        print(ans)


main()


### FIXED CODE ###

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    start = time.time()
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        now = time.time()
        if now - start > 1.9:
            ans = M
            break
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print(-1)
    else:
        print(ans)


main()
### BUGGY CODE ###

h , w = map(int,input().split())
giri = [list(input()) for i in range(h)]
ans = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    sta = -1
    cou = 0
    for j in range(w):
        if sta == -1 and giri[i][j] == ".":
            sta = j
            cou += 1
        elif sta != -1 and giri[i][j] == ".":
            cou += 1
        elif sta != -1 and giri[i][j] == "#":
            for k in range(sta,j):
                ans[i][k] += cou
            cou = 0
            sta = -1
        if j == w-1 and sta != -1:
            for k in range(sta,w):
                ans[i][k] += cou

for i in range(w):
    sta = -1
    cou = 0
    for j in range(h):
        if sta == -1 and giri[j][i] == ".":
            sta = j
            cou += 1
        elif sta != -1 and giri[j][i] == ".":
            cou += 1
        elif sta != -1 and giri[j][i] == "#":
            for k in range(sta,j):
                ans[k][i] += cou
            cou = 0
            sta = -1
        if j == h-1 and sta != -1:
            for k in range(sta,h):
                ans[k][i] += cou

kotae = 0

for i in range(h):
    for j in range(w):
        kotae = max(kotae,ans[i][j]-1)

print(kotae)

### FIXED CODE ###

h , w = map(int,input().split())
giri = [list(input()) for i in range(h)]
ans = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    sta = -1
    cou = 0
    for j in range(w):
        if sta == -1 and giri[i][j] == ".":
            sta = j
            cou += 1
        elif sta != -1 and giri[i][j] == ".":
            cou += 1
        elif sta != -1 and giri[i][j] == "#":
            for k in range(sta,j):
                ans[i][k] += cou
            cou = 0
            sta = -1
        if j == w-1 and sta != -1:
            for k in range(sta,w):
                ans[i][k] += cou

for i in range(w):
    sta = -1
    cou = 0
    for j in range(h):
        if sta == -1 and giri[j][i] == ".":
            sta = j
            cou += 1
        elif sta != -1 and giri[j][i] == ".":
            cou += 1
        elif sta != -1 and giri[j][i] == "#":
            for k in range(sta,j):
                ans[k][i] += cou
            cou = 0
            sta = -1
        if j == h-1 and sta != -1:
            for k in range(sta,h):
                ans[k][i] += cou

kotae = 0

for i in range(h):
    for j in range(w):
        kotae = max(kotae,ans[i][j]-1)

print(kotae)
### BUGGY CODE ###

N = int(input())
S = input()
def Zalgo(S):
    N = len(S)
    A = [0]*N
    A[0] = N
    i = 1
    j = 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + A[k] < j:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A
res = 0
for i in range(N - 1):
    lcp = Zalgo(S[i:])
    for j in range(N - i):
        l = min(j, lcp[j])
        res = max(l, res)
print(res)

### FIXED CODE ###

N = int(input())
S = input()
r = 1
ans = 0
for i in range(N):
    while True:
        if S.rfind(S[i : r + 1]) >= r + 1:
            r += 1
            ans = max(ans, r - i)
        else:
            break
print(ans)
### BUGGY CODE ###

import heapq
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def ii(): return int(stdin.readline())
def li(): return map(int, stdin.readline().split())
N, M = tuple(li())
A = list(li())
heapq.heapify(A)
def update(pq, k, val):
    # update pq in place
    for _ in range(k):
        cur = heapq.heappop(pq)
        if cur < val:
            heapq.heappush(pq, val)
        else:
            heapq.heappush(pq, cur)
            break

ops = [tuple( li() ) for _ in range(M)]
ops.sort(key=lambda x:x[-1])
for k, val in ops:
    update(A, k, val)

print(sum(A))


### FIXED CODE ###

import heapq
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def ii(): return int(stdin.readline())
def li(): return map(int, stdin.readline().split())
N, M = tuple(li())
A = list(li())
heapq.heapify(A)
def update(pq, k, val):
    # update pq in place
    for _ in range(k):
        cur = heapq.heappop(pq)
        if cur < val:
            heapq.heappush(pq, val)
        else:
            heapq.heappush(pq, cur)
            break

ops = []
# val, k_sum
keep = dict()
for i in range(M):
    k, val = tuple(li())
    k_sum = keep.get(val, 0)
    keep[val] = k_sum + k

for val, k in keep.items():
    update(A, k, val)

print(sum(A))
### BUGGY CODE ###

import numpy as np
from functools import reduce
import math

def gcd(*numbers):
    return reduce(math.gcd, numbers)

a = int(input())
result = 0
for i in range(1, a+1):
  for j in range(1, a+1):
    for k in range(1, a+1):
      result += gcd(i, j, k)
      
print(result)

### FIXED CODE ###

from functools import reduce
import math

#def gcd(*numbers):
#    return reduce(math.gcd, numbers)

a = int(input())
result = 0

for i in range(1, a+1):
  for j in range(1, a+1):
    for k in range(1, a+1):
      result += math.gcd(math.gcd(i, j),k)
      
print(result)
### BUGGY CODE ###

n=int(input())
a=list(input().split())
if n%2==0:
  b=a[-1::-2]+a[0::2]
else:
  b=a[-1::-2]+a[1::2]
ans=''
for i in range(n):
  ans+=b[i]+' '
print(ans[:-1])

### FIXED CODE ###

n=int(input())
a=list(input().split())
if n%2==0:
  b=a[-1::-2]+a[0::2]
else:
  b=a[-1::-2]+a[1::2]
ans=''
for i in range(n):
  ans+=b[i]+' '
print(ans[:-1])
### BUGGY CODE ###

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

max = 0
flag = bool(0)
for i in range(n - 1):
    flag = bool(0)
    count = 0
    for j in range(i, n - 1):
        if h[j] >= h[j + 1]:
            count += 1
            if count > max:
                max = count
        else:
            break

print(max)


### FIXED CODE ###

import sys
n = int(input())
h = list(map(int, input().split()))

max = 0
max_i = 0
count = 0
for i in range(n - 1):
    if h[i] >= h[i + 1]:
        count += 1
        if count > max:
            max = count
    else:
        count = 0

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

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = input()

    ans = 0
    for p in range(1000):
        p = str(p).zfill(3)

        i = 0
        for j in range(N):
            if S[j] == p[i]:
                i += 1

                if i == 3:
                    ans += 1
                    break

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = list(input())
    ans = 0

    for p in range(1000):
        p = str(p).zfill(3)
        i = 0
        for j in range(N):
            if p[i] == S[j]:
                i += 1
            if i == 3:
                ans += 1
                break

    print(ans)


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

N,W = map(int,input().split())
K = 10**5
dp = [[10**100 for i in range(K+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = map(int,input().split())
    for j in range(K+1):
        dp[i][j] = dp[i-1][j]
        if j < v:
            continue
        else:
            dp[i][j] = min(dp[i-1][j-v] + w,dp[i-1][j])
for i in range(K+1):
    x = dp[N][-i-1]
    if x <= W:
        print(K-i)
        quit()

### FIXED CODE ###

N,W = map(int,input().split())
K = 10**5
dp = [[10**100 for i in range(K+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = map(int,input().split())
    for j in range(K+1):
        dp[i][j] = dp[i-1][j]
        if j < v:
            continue
        else:
            dp[i][j] = min(dp[i-1][j-v] + w,dp[i-1][j])
for i in range(K+1):
    x = dp[N][-i-1]
    if x <= W:
        print(K-i)
        quit()
### BUGGY CODE ###

import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202006_5th/D_input.txt")
else:
    f=sys.stdin
ans=1
n=int(f.readline().strip())
prime=[]
# Start from where n is equal to 2
for _ in range(1,n):
    number_of_multiply = []
    tmp=_+1
    for __ in prime:
        cnt=0
        if tmp<=1:
            break
        while (tmp%__)==0:
            cnt+=1;tmp=int(tmp/__);
        if cnt>0:
            number_of_multiply.append(cnt)
    if len(number_of_multiply)==0:
        prime.append(_+1)
        ans+=(_+1)*2
    else:
        num_of_divisor=1
        for ___ in number_of_multiply:
            num_of_divisor*=___+1
        ans+=(_+1)*num_of_divisor
print(ans)

### FIXED CODE ###

import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202006_5th/D_input.txt")
else:
    f=sys.stdin
ans_sum=0
n=int(f.readline().strip())
for _ in range(1,n+1):
    num=n//_
    ans_sum+=_*((num*(num+1))//2)
print(ans_sum)
### BUGGY CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (M + 1) for _ in range(N + 1)]  # dp[s][t]

for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        v = dp[i - 1][j] + dp[i][j - 1]
        if s == t:
            v += 1
        else:
            v -= dp[i - 1][j - 1]
        dp[i][j] = v % MOD

print((dp[-1][-1] + 1) % MOD)


### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (M + 1) for _ in range(N + 1)]  # dp[s][t]

for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        v = dp[i - 1][j] + dp[i][j - 1]
        if s == t:
            v += 1
        else:
            v -= dp[i - 1][j - 1]
        dp[i][j] = v % MOD

print((dp[-1][-1] + 1) % MOD)
### BUGGY CODE ###

a,b=map(int,input().split())
l=range(a,b+1)
ans=1
for i in range(len(l)):
  ans=ans*l[i]
if ans>0:
  print("Positive")
if ans<0:
  print("Negative")
if ans==0:
  print("Zero")

### FIXED CODE ###

a,b=map(int,input().split())
if (a>0 and b>0):
	print("Positive")
elif (a>=0 and b<=0) or (a<=0 and b>=0):
	print("Zero")
elif (a<0 and b<0 and (a+b)%2==0):
	print("Negative")
else:
	print("Positive")
### BUGGY CODE ###

n = int(input())
la = list(map(int, input().split()))
for i in range(n):
  print(la.count(i+1))

### FIXED CODE ###

import collections
n = int(input())
la = list(map(int, input().split()))
c = collections.Counter(la)

for i in range(1,n+1):
  print(c[i])