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

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
ans = int(0)

N, M = LI()
S = LI()
T = LI()
dp = [[0]*(M+1) for _ in range(N+1)]
sumdp = [[0]*(M+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            dp[i][j] = sumdp[i-1][j-1]+1
            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1] + dp[i][j]
        #累積和の更新
        else:
            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1]
#        ans += dp[i][j]
#print(dp)
#for row in dp:
#    ans+= sum(row)%mod
print((sumdp[N][M]+1)%mod)

### FIXED CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
ans = int(0)

N, M = LI()
S = LI()
T = LI()
dp = [[0]*(M+1) for _ in range(N+1)]
sumdp = [[0]*(M+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            dp[i][j] = sumdp[i-1][j-1]+1
            sumdp[i][j] = sumdp[i - 1][j] + sumdp[i][j - 1] +1
#            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1] + dp[i][j]
        #累積和の更新
        else:
            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1]
        sumdp[i][j] %=mod
#        ans += dp[i][j]
#print(dp)
#for row in dp:
#    ans+= sum(row)%mod
print((sumdp[N][M]+1)%mod)
### BUGGY CODE ###

#16:15
n = int(input())
xyi = []
for i in range(n):
  xyi.append(list(map(int,input().split())) + [i])
xyi.sort()
road = []
for j in range(n-1):
  road.append([xyi[j+1][0]-xyi[j][0],xyi[j][2],xyi[j+1][2]])
xyi.sort(key = lambda x: x[1])
for j in range(n-1):
  road.append([xyi[j+1][1]-xyi[j][1],xyi[j][2],xyi[j+1][2]])
road.sort()
pre = [i for i in range(n)]
ans = 0
for k in range(2*n-2):
  d,I,J = road[k]
  while pre[I] != I:
    I = pre[I]
  while pre[J] != J:
    J = pre[J]
  if I != J:
    pre[J] = I
    ans += d
print(ans)

### FIXED CODE ###

#16:15
n = int(input())
xyi = []
for i in range(n):
  xyi.append(list(map(int,input().split())) + [i])
xyi.sort()
road = []
for j in range(n-1):
  road.append([xyi[j+1][0]-xyi[j][0],xyi[j][2],xyi[j+1][2]])
xyi.sort(key = lambda x: x[1])
for j in range(n-1):
  road.append([xyi[j+1][1]-xyi[j][1],xyi[j][2],xyi[j+1][2]])
road.sort()
pre = [i for i in range(n)]
ans = 0
for k in range(2*n-2):
  d,I,J = road[k]
  ii = []
  jj = []
  while pre[I] != I:
    ii.append(I)
    I = pre[I]
  for Is in ii:
    pre[Is] = I
  while pre[J] != J:
    jj.append(J)
    J = pre[J]
  for Js in jj:
    pre[Js] = J
  if I != J:
    pre[J] = I
    ans += d
print(ans)
### BUGGY CODE ###

import numpy as np

s = int( input() )
ss = str( s )
l = len( ss )
#print( s, l )

ans = int( 0 )
for i in range( l-4 ):
    for j in range( i+4, l+1 ):
        ssij = ss[ i:j ]
        sij = int( ssij )
#        print( i, j, sij )
        if sij % 2019 == 0:
#            print( "Yes" )
            ans = ans + 1

print( ans )


### FIXED CODE ###

import numpy as np

s = input()

d = [ int( 0 ) ] * 2019
d[ 0 ] = int( 1 )
r = int( 0 )
t = int( 1 )

for si in reversed( s ):
#    print( si )

    r = int( si ) * t + r
    r = r % 2019

    t = t * 10
    t = t % 2019

    d[ r ] = d[ r ] + 1

ans = int( 0 )
for di in d:
    ans = ans + di * ( di - 1 ) // 2

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

N,X=map(int,input().split())
inputcities=list(map(int, input().split()))
cities=[abs(inputcities[i]-X) for i in range(N)]
count=0
flag=0
minimum=min(cities)
for j in range(minimum+1)[::-1]:
  for i in range(N):
    if cities[i]%j==0:
      count+=1
    else:
      count=0
      break
    if count==N:
      print(j)
      flag=1
      break
  if flag==1:
    break

### FIXED CODE ###

def gcd(a,b):
    if a < b:
        a,b = b,a
    if a % b == 0:
        return b
    else:
        return gcd(b,(a % b))
 
N,X=map(int,input().split())
inputcities=list(map(int, input().split()))
cities=[abs(inputcities[i]-X) for i in range(N)]
cities.sort()
D=cities[0]
for i in range(N):
  D=gcd(D,cities[i])
print(D)
### BUGGY CODE ###

def comb(n,r):
    return (((fact_list[n]*inv_fact_list[n-r])%998244353)*inv_fact_list[r])%998244353
def inv(n):
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*n)%998244353
        n=(n**2)%998244353
    return s

fact_list=[1 for i in range(300001)]
inv_fact_list=[1 for i in range(300001)]
for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353
    inv_fact_list[i]=inv(fact_list[i])

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n):
    if (k-a*i)%b==0 and (k-a*i)//b<=n:
        res+=comb(n,i)*comb(n,(k-a*i)//b)
        res%=998244353
print(res)

### FIXED CODE ###

fact_list=[None]*300001
inv_fact_list=[None]*300001
fact_list[0]=1
inv_fact_list[0]=1
"""
def inv(n):
    if inv_fact_list[n]!=None:
        return inv_fact_list[n]
    m=fact_list[n]
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*m)%998244353
        m=(m**2)%998244353
    inv_fact_list[n]=s
    return s
def enc(n):
    if n==0:
        return "("
    s=""
    while n>0:
        s+=chr(n%86+40)
        n//=86
    return s
 
def dec(s):
    n=0
    for i in range(len(s)):
        n+=(86**i)*(ord(s[i])-40)
    return n
"""
def comb(n,r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    if inv_fact_list[n-r]!=None:
        invnr=inv_fact_list[n-r]
    else:
        m=fact_list[n-r]
        invnr=1
        for i in range(30):
            if i!=23 and i!=26:
                invnr=(invnr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[n-r]=invnr
    if inv_fact_list[r]!=None:
        invr=inv_fact_list[r]
    else:
        m=fact_list[r]
        invr=1
        for i in range(30):
            if i!=23 and i!=26:
                invr=(invr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[r]=invr
    return (((fact_list[n]*invnr)%998244353)*invr)%998244353
 
for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353
 
s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n+1):
    if k-a*i<0:
        break
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res=(res+comb(n,i)*comb(n,(k-a*i)//b))%998244353
print(res)
### BUGGY CODE ###

S = input()
ans = [1] * len(S)
N = len(S)
prev = ans
prev_prev = None
counter = 0
while True:
    new_ans = [0] * len(ans)
    for i in range(N):
        if i == 0:
            new_ans[i] = ans[i + 1] if S[i + 1] == 'L' else 0
        elif i == N - 1:
            new_ans[i] = ans[i - 1] if S[i - 1] == 'R' else 0
        else:
            lv = ans[i - 1] if S[i - 1] == 'R' else 0
            rv = ans[i + 1] if S[i + 1] == 'L' else 0
            new_ans[i] = lv + rv
    # print(new_ans)

    if prev_prev is None:
        prev_prev = ans
        prev = new_ans
        ans = new_ans
    else:
        prev_prev = prev
        prev = ans
        ans = new_ans

    if prev_prev == ans:
        break
    ans = new_ans
    counter += 1

if counter % 2 == 0:
    print(*prev)
else:
    print(*ans)


### FIXED CODE ###

# 解説を読んでからrun-length
# TLEだったので見て修正

import bisect

S = input()
RL = []
for i in range(len(S) - 1):
    if S[i] == 'R' and S[i + 1] == 'L':
        RL.append(i)


ans = [0] * len(S)
for i in range(len(S)):
    idx = bisect.bisect_left(RL, i)
    if S[i] == 'L':  # Lだと見つかった場所の←へ行く
        mark = RL[idx - 1]
    else: # Rだと見つかった場所の→へ行く
        mark = RL[idx]

    if (i - mark) % 2 == 0: # Rの位置から偶数離れていればRの方
        ans[mark] += 1
    else: # 奇数離れていればLの位置へ行く
        ans[mark + 1] += 1

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

import itertools

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

ans = 0
L.sort()

for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if L[k] < L[i]+L[j]:
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

import bisect

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

ans = 0
L.sort()

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        idx = bisect.bisect_left(L, L[i] + L[j])
        ans += max(0, idx - j - 1)
print(ans)
### BUGGY CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
 



sys.setrecursionlimit(10 ** 6)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = [[] for i in range(n + 1)]

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].append(b)
    g[b].append(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)


### FIXED CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
 



sys.setrecursionlimit(10 ** 6)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = [[] for i in range(n + 1)]

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].append(b)
    g[b].append(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)
### BUGGY CODE ###

n = int(input())
lst = []
num = [1]*n
ans = 0
for i in range(n):
    s = sorted(input())
    if s not in lst:
        lst.append(s)
    else:
        pos = lst.index(s)
        num[pos] += 1
for j in num:
    ans += (j * (j-1)) / 2
print(int(ans))

### FIXED CODE ###

from collections import defaultdict
N = int(input())
dict = defaultdict(int)
ans = 0
for i in range(N):
    s = ''.join(sorted(input()))
    ans += dict[s]
    dict[s] += 1
print(ans)
### BUGGY CODE ###

from collections import deque

n,k=map(int,input().split())
visited=[False]*n
color=[0]*n
visited[0]=True
color[0]=k
mod=10**9+7

graph=[[] for i in range(n)]

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


Q=deque()
Q.append((0))

while Q:
  p=Q.pop()
  visited[p]=True
  ans=k
  for i in graph[p]:
      if visited[i]==False:
          Q.append((i))
      
      else:
          ans-=1

      for j in graph[i]:
          if j==p:
              continue
          if visited[j]:
              ans-=1
    
  color[p]=ans


ans=1

for i in color:
    ans*=i
    ans%=mod


print(ans)

### FIXED CODE ###

from collections import deque

n,k=map(int,input().split())
visited=[False]*n
visited[0]=True
color=[0]*n
color[0]=k
mod=10**9+7

graph=[[] for i in range(n)]

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


Q=deque()
Q.append((0))
ans=k

while Q:
  p=Q.pop()
  cnt=0
  for i in graph[p]:
    if visited[i]==False:
        cnt+=1
        Q.append((i))
        visited[i]=True

  if p==0:
      for i in range(cnt):
          ans*=k-i-1
          ans%=mod

  else:
      for i in range(cnt):
          ans*=k-i-2
          ans%=mod


print(ans%mod)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2) for _ in range(H+2)]
#queue = []
queue = deque()
for i in range(H):
  line = input().strip()
  for j,ch in enumerate(line):
    if ch == "#":
      queue.append((i+1,j+1))
    else:
      mark_matrix[i+1][j+1] = False
  
#print(mark_matrix)
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))

  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
#mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
#  line = input()
#  for j,ch in enumerate(line):
#    if ch == "#":
#      mark_matrix[i+1][j+1] = True
#      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)
### BUGGY CODE ###

n = int(input())
li = map(int,input().split())
ans=1
for i in li:
    ans*=i
    if ans>10**18:
        ans=-1
if ans<0:
    ans=-1
print(ans)

### FIXED CODE ###

n = int(input())
li = map(int,input().split())
ans=1
mx=10**18
for i in li:
    ans*=i
    if ans>mx:
        ans=-1
        break
for i in li:
    if i==0:
        ans=0
        break
print(ans)
### BUGGY CODE ###

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

l = []
i = 0
j = 0
s = 0
while i < a:
    l.append(1)
    i += 1
while j < b:
    l.append(0)
    j += 1
while s < c:
    l.append(-1)
    s += 1

print(sum(l[0:k]))




### FIXED CODE ###

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

print(min(k, a) - max(k - a - b, 0))
### BUGGY CODE ###

n=int(input())
p=[]
for i in range (n):
	p.append(int(input()))
pos=0
num=0
n_th = 0
for i in range(n):
	if i+1 in p[pos:]:
		num += 1
		pos = p[pos:].index(i+1)+pos
	else:
		if num>n_th:
			n_th = num
		if i+1 in p:
			num = 1
			pos = p.index(i+1)
if num >n_th:
	print (n-num)
else:
	print(n-n_th)


### FIXED CODE ###

n=int(input())
p=[]
for i in range (n):
	p.append(int(input()))
pos=0
num=0
n_th = 0
s={}
for i in p:
	if i-1 in s:
		s[i]=s[i-1]+1
	else:
		s[i]=1
print(n-max(s.values()))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

def power(x, y):
   if y == 0:
       return 1
   elif y == 1:
       return x % mod
   elif y % 2 == 0:
       return power(x, y/2) ** 2 % mod
   else:
       return power(x, (y-1)/2) ** 2 * x % mod

def sum_dp(l):
	tmp = 0
	for i, x in enumerate(l[N]):
		if i >= sum_a/2:
			tmp = (tmp + x)%mod
	return tmp

N = INT()
a = [INT() for _ in range(N)]

sum_a = sum(a)
dp = [[0]*(sum_a+1) for _ in range(N+1)]
dp[0][0] = 1

dp2 = [[0]*(sum_a+1) for _ in range(N+1)]
dp2[0][0] = 1

for i, x in enumerate(a):
	for j in range(sum_a+1):
		if j+x >= sum_a+1:
			continue
		dp[i+1][j] = (dp[i+1][j] + dp[i][j]*2)%mod # 赤以外に塗り分ける
		dp[i+1][j+x] = (dp[i+1][j+x] + dp[i][j])%mod # 赤に塗り分ける
		dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j])%mod
		dp2[i+1][j+x] = (dp2[i+1][j+x] + dp2[i][j])%mod
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	# print((power(3, N)-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2])+3*dp2[N][sum_a//2])%mod)
	print((power(3, N)-3*sum_dp(dp)+3*dp2[N][sum_a//2])%mod)
else:
	# print((power(3, N)-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2+1]))%mod)
	print((power(3, N)-3*sum_dp(dp))%mod)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

def power(x, y):
   if y == 0:
       return 1
   elif y == 1:
       return x % mod
   elif y % 2 == 0:
       return power(x, y/2) ** 2 % mod
   else:
       return power(x, (y-1)/2) ** 2 * x % mod

N = INT()
a = np.array([INT() for _ in range(N)])

sum_a = np.sum(a)
dp = np.zeros((N+1, sum_a+1))
dp[0][0] = 1

dp2 = np.zeros((N+1, sum_a//2+1))
dp2[0][0] = 1

for i, x in enumerate(a):
	dp[i+1, :] += dp[i, :]*2 % mod # 赤以外に塗り分ける
	dp[i+1, x:] += dp[i, :-x] % mod # 赤に塗り分ける
	dp2[i+1,:] += dp2[i, :] % mod
	dp2[i+1, x:] += dp2[i, :-x] % mod
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2:])+3*dp2[N,sum_a//2])%mod))
else:
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2+1:]))%mod))
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
mod = 10**9+7
SUM = 0

maxA = max(A)
d = 0
while 1:
    if maxA < 2**d:
        break
    d += 1

BitA = [[0]*d for _ in range(N)]
for i in range(N):
    BitA[i] = list(map(int, format(bin(A[i])[2:], '0>{}'.format(d))))

BitSumB = 0
for i in range(d):
    tmp = sum([BitA[j][i] for j in range(N)])
    BitSumB += 2 ** (d-i-1) * (tmp * (N - tmp))
    #BitSumB = BitSumB % mod

print(BitSumB%mod)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
mod = 10**9+7
SUM = 0

maxA = max(A)
d = 0
while 1:
    if maxA < 2**d:
        break
    d += 1

BitSumB = 0
for i in range(d):
    tmp = 0
    for n in range(N):
        tmp += (A[n] >> i) & 1
    BitSumB += (2**i) * tmp * (N - tmp)



"""
BitA = [[0]*d for _ in range(N)]
for i in range(N):
    BitA[i] = list(map(int, format(bin(A[i])[2:], '0>{}'.format(d))))

BitSumB = 0
for i in range(d):
    tmp = sum([BitA[j][i] for j in range(N)])
    BitSumB += 2 ** (d-i-1) * (tmp * (N - tmp))
    #BitSumB = BitSumB % mod
"""

print(BitSumB % mod)
### BUGGY CODE ###

#D
N,W=map(int,input().split())
w_list=[]
v_list=[]

for i in range(N):
    w1,v1=map(int,input().split())
    w_list.append(w1)
    v_list.append(v1)
inf=float("inf")
dp=[[-inf for i in range(W+1)] for j in range(N+1)]
for i in range(W+1): dp[0][i]=0

for i in range(N):
    for w in range(W+1):
        if w_list[i]<=w:
            dp[i+1][w]=max(dp[i][w-w_list[i]]+v_list[i],dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[N][W])

### FIXED CODE ###

#D
N,W=map(int,input().split())
w_list=[]
v_list=[]

for i in range(N):
    w1,v1=map(int,input().split())
    w_list.append(w1)
    v_list.append(v1)
inf=float("inf")
dp=[[-inf for i in range(W+1)] for j in range(N+1)]
for i in range(W+1): dp[0][i]=0

for i in range(N):
    for w in range(W+1):
        if w_list[i]<=w:
            dp[i+1][w]=max(dp[i][w-w_list[i]]+v_list[i],dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[N][W])
### BUGGY CODE ###

n, p=map(int,input().split())
ans = 0
for i in range(1, p+1):
    ni = i**n
    if p/ni >= 1 and p/ni == int(p/ni):
        ans = i
    elif p/ni < 1:
        break
print(ans)

### FIXED CODE ###

n, p=map(int,input().split())
ans = 0
if n != 1:
    for i in range(1,int((p+1)**(1/n))+1):
        ni = i**n
        if p/ni >= 1 and p/ni == int(p/ni):
            ans = i
        elif p/ni < 1:
            break
    print(ans)
else:
    print(p)
### BUGGY CODE ###

N = int(input())
S = str(input())

ans = 0
for i in range(1000):
  z = str(i).zfill(3)
  right = -1
  center = -1
  for r in range(1, N-1):
    if S[N-r] == z[2]:
      right = N-r
      break
  if right == -1:
    continue
  for c in range(1, right):
    if S[right-c] == z[1]:
      center = right-c
      break
  if center == -1:
    continue
  for l in range(1, center+1):
    if S[center-l] == z[0]:
      ans += 1
      break
print(ans)

### FIXED CODE ###

N = int(input())
S = str(input())
R = S[::-1]

ans = 0
for i in range(1000):
  z = str(i).zfill(3)
  right = -1
  left = -1
  if z[2] in R:
    r = R.index(z[2]) + 1
    right = N-r
  else:
    continue
  if z[0] in S:
    left = S.index(z[0]) + 1
  else:
    continue
  if z[1] in S[left:right]:
    ans += 1
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
r=m//n
for i in range(r):
  if m%(r-i)==0 and m//(r-i)>=n:
    print(r-i)
    break

### FIXED CODE ###

n,m=map(int,input().split())
r=m//n
if r>=10**7:
  for i in range(n,r):
    if m%i==0:
      print(m//i)
      break
else:
  for i in range(r):
    if m%(r-i)==0 and m//(r-i)>=n:
      print(r-i)
      break
### BUGGY CODE ###

L,R=map(int,input().split())
#print(L,R)  

COUNT=2019
NUMBER=0

for i in range(L,R+1):
  for j in range(i+1,R+1):
    
    NUMBER=i*j%2019
    #print(i,j,NUMBER)
    if COUNT>NUMBER:
      COUNT=NUMBER
      #print(i,j,NUMBER)

    
print(COUNT)

### FIXED CODE ###

L,R=map(int,input().split())

R=min(R,L+2019)
#print(L,R)  
 
COUNT=2019
NUMBER=0
 
for i in range(L,R+1):
  for j in range(i+1,R+1):
    
    NUMBER=i*j%2019
    #print(i,j,NUMBER)
    if COUNT>NUMBER:
      COUNT=NUMBER
      #print(i,j,NUMBER)
 
    
print(COUNT)