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

#import itertools
import math
n = int(input())
a = input().split()
a = [int(m) for m in a]
mod = 10**9 + 7
dic = {}
dic2 = {}
for i in range(n + 1):
    dic[a[i]] = 0
    dic2[a[i]] = []
k = 0
j = 0
for i in range(n + 1):
    dic[a[i]] += 1
    dic2[a[i]].append(i)
    if dic[a[i]] == 2:
        j = dic2[a[i]][0]
        k = i

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(n + 1):
    if i == 0:
        print(n)
    else:
        if j + n - k >= i:
            print((combinations_count(n + 1, i + 1) - combinations_count(j + n - k, i)) % mod)
        else:
            print(combinations_count(n + 1, i + 1) % mod)

### FIXED CODE ###

#import itertools
import math
n = int(input())
a = input().split()
a = [int(m) for m in a]
dic = {}
dic2 = {}
for i in range(n + 1):
    dic[a[i]] = 0
    dic2[a[i]] = []
k = 0
j = 0
for i in range(n + 1):
    dic[a[i]] += 1
    dic2[a[i]].append(i)
    if dic[a[i]] == 2:
        j = dic2[a[i]][0]
        k = i

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

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

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


for i in range(n + 1):
    if i == 0:
        print(n)
    else:
        if j + n - k >= i:
            if (cmb(n + 1, i + 1, mod) - cmb(j + n - k, i, mod)) >= 0:
                print(cmb(n + 1, i + 1, mod) - cmb(j + n - k, i, mod))
            else:
                print(cmb(n + 1, i + 1, mod) - cmb(j + n - k, i, mod) + mod)
        else:
            print(cmb(n + 1, i + 1, mod))
### BUGGY CODE ###

R, C, K = map(int, input().split())
V = [[0] * (R + 1) for _ in range(C + 1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[c][r] = v

X = [[0] * 4 for _ in range(R + 1)]
for i in range(1, C + 1):
    Vi = V[i]
    for j in range(1, R + 1):
        v = Vi[j]
        Xj = X[j]
        if v:
            Xj[3] = max(Xj[3], Xj[2] + v)
            Xj[2] = max(Xj[2], Xj[1] + v)
            Xj[0] = max(Xj[0], max(X[j-1]))
            Xj[1] = max(Xj[1], Xj[0] + v)
        else:
            Xj[0] = max(Xj[0], max(X[j-1]))

print(max(X[R]))

### FIXED CODE ###

R, C, K = map(int, input().split())
V = [[0] * (R + 1) for _ in range(C + 1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[c][r] = v

X = [[0] * 4 for _ in range(R + 1)]
for i in range(1, C + 1):
    Vi = V[i]
    for j in range(1, R + 1):
        v = Vi[j]
        Xj = X[j]
        if v:
            Xj[3] = max(Xj[3], Xj[2] + v)
            Xj[2] = max(Xj[2], Xj[1] + v)
            Xj[0] = max(Xj[0], max(X[j-1]))
            Xj[1] = max(Xj[1], Xj[0] + v)
        else:
            Xj[0] = max(Xj[0], max(X[j-1]))

print(max(X[R]))
### BUGGY CODE ###

import math

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

for i in range(M):
    A[-1] /= 2
    A = sorted(A)

for j in range(N):
    A[j] = math.floor(A[j])

print(sum(A))


### FIXED CODE ###

from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
A = list(map(int, input().split()))
A_minus = [-x for x in A]
heapify(A_minus)

for i in range(M):
    n = -heappop(A_minus) // 2
    heappush(A_minus, -n)

print(-sum(A_minus))
### BUGGY CODE ###

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.append(0)
X.sort()
ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0 for i in range(ma+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  cnt=X[i]
  for j in range(1,N+1):
    for k in range(ma+1):
      if k < cnt:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  if x*A<=ma:
    ans+=dp[N][x][x*A]
print(ans)


### FIXED CODE ###

def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = list(input().rstrip())
ord_a = ord("a")

# N: 処理する区間の長さ
INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [[0]*(2*N0) for _ in range(26)]
lazy = [[0]*(2*N0) for _ in range(26)]

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(k, *ids):
    for i in reversed(ids):
        v = lazy[k][i-1]
        if not v:
            continue
        lazy[k][2*i-1] += v; lazy[k][2*i] += v
        data[k][2*i-1] += v; data[k][2*i] += v
        lazy[k][i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x, k):
    *ids, = gindex(l, r)
    propagates(k, *ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[k][R-1] += x; data[k][R-1] += x
        if L & 1:
            lazy[k][L-1] += x; data[k][L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[k][i-1] = max(data[k][2*i-1], data[k][2*i])

# 区間[l, r)内の最大値を求める
def query(l, r, k):
    propagates(k, *gindex(l, r))
    L = N0 + l; R = N0 + r

    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[k][R-1])
        if L & 1:
            s = max(s, data[k][L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for j in range(N):
    u = S[j]
    update(j, N, 1, ord(u) - ord_a)

Q = int(input())

for _ in range(Q):
    q = input().rstrip().split()
    if q[0] == "2":
        l, r = int(q[1]) - 1, int(q[2]) - 1
        cnt = 0
        for i in range(26):
            if l == 0:
                cnt += int(query(r, r + 1, i) > 0)
            else:
                cnt += int((query(r, r + 1, i) - query(l - 1, l, i) > 0))

        print(cnt)
    else:
        i, c = int(q[1]) - 1, q[2]
        update(i, N, -1, ord(S[i]) - ord_a)
        S[i] = c
        update(i, N, 1, ord(S[i]) - ord_a)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = list(input().rstrip())
ord_a = ord("a")

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

bits = [Bit(N) for _ in range(26)]

for i in range(N):
    s = S[i]
    bits[ord(s) - ord_a].add(i + 1, 1)

Q = int(input())

for _ in range(Q):
    query = input().rstrip().split()
    if query[0] == "1":
        i, c = int(query[1]), query[2]
        bits[ord(S[i - 1]) - ord_a].add(i, -1)
        S[i - 1] = c
        bits[ord(S[i - 1]) - ord_a].add(i, 1)
    else:
        l, r = int(query[1]), int(query[2])
        res = 0
        for bit in bits:
            if l != 1:
                res += int(bit.sum(r) - bit.sum(l - 1) > 0)
            else:
                res += int(bit.sum(r) > 0)
        print(res)
### BUGGY CODE ###

a, b, c = map(int, input().split())
i = 0
while a%2==0 or b%2==0 or c%2==0 or i<10*3:
    at = a//2
    bt = b//2
    ct = c//2
    a = bt + ct
    b = at + ct
    c = at + bt
    i+=1
if i > 10**3:
    print(-1)
else:
    print(i)

### FIXED CODE ###

a, b, c = map(int, input().split())
i = 0
f = True
while a%2==0 and b%2==0 and c%2==0:
    at = a//2
    bt = b//2
    ct = c//2
    a = bt + ct
    b = at + ct
    c = at + bt
    i+=1
    if a == b == c:
        print(-1)
        f = False
        break
if f:
    print(i)
### BUGGY CODE ###

N, Q = map(int, input().split())
s = input()
lis = []
for i in range(len(s)-1):
    if(s[i:i+2] == "AC"): lis.append(i)
n = len(lis)
for i in range(Q):
    cnt = 0
    in0, in1 = map(int, input().split())
    for j in lis:
        if((in0-1)<= j < (in1-1)): cnt += 1
    print(cnt)


### FIXED CODE ###

N, Q = map(int, input().split())
s = input()
nlis = [0]
cnt = 0
for i in range(len(s)-1):
    if(s[i:i+2] == "AC"): 
        cnt += 1
    nlis.append(cnt)
#print(nlis)
for i in range(Q):
    in0, in1 = map(int, input().split())
    print(nlis[in1-1]-nlis[in0-1])
### BUGGY CODE ###

import sys

x = int(input())

for i in range(-2000, 2000):
    for j in range(-2000, 2000):
        if i ** 5 - j ** 5 == x:
            print(i, j)
            sys.exit()


### FIXED CODE ###

import sys

x = int(input())

for i in range(-1000, 1000):
    for j in range(-1000, 1000):
        if i ** 5 - j ** 5 == x:
            print(i, j)
            sys.exit()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def solve():
    N, K = map(int, input().split())
    N_1 = [set() for _ in range(N+1)]
    N_2 = [set() for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        N_2[a] |= N_1[b] | {b}
        N_2[b] |= N_1[a] | {a}
        for n in N_1[b]:
            N_2[n].add(a)
        for n in N_1[a]:
            N_2[n].add(b)
        N_1[a].add(b)
        N_1[b].add(a)
    checked = set()
    q = {1}
    res = 1
    while q:
        n = q.pop()
        q |= N_1[n] - checked
        res *= K - len(N_2[n] & checked)
        checked.add(n)
        if res < 0:
            return str(0)
        else:
            res %= 10**9+7
    return str(res)


if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
def solve():
    N, K = map(int, input().split())
    N_1 = [{1},{0}]+[set() for _ in range(N-1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        N_1[a].add(b)
        N_1[b].add(a)
    checked, q = set(), {0}
    res = 1
    while q:
        n = q.pop()
        checked.add(n)
        q.update(set.difference(N_1[n], checked))
        K_ = K-min(2,n)
        for i in range(len(N_1[n])-(n>0)):
            if K_ == i:
                return str(0)
            res = (res*(K_-i))%(10**9+7)
    return str(res)
if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

S=__import__('collections').deque(input())
for _ in range(int(input())):
	T=input()
	if T<'2':S.reverse()
	else:(S.appendleft if T[2]<'2' else S.append)(T[4])
print(*S,sep='')

### FIXED CODE ###

S,f=__import__('collections').deque(input()),0
for _ in range(int(input())):
	T=input()
	if T<'2':f=1-f
	else:(S.appendleft if (T[2]<'2')^f else S.append)(T[4])
if f:S.reverse()
print(*S,sep='')
### BUGGY CODE ###

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

arr = [0] * (n+1)
arr[0] = 1
for i in range(1, n+1):
    if i in a:
        arr[i] = 0
    else:
        arr[i] = (arr[i-1] + arr[i-2]) % 1000000007

print(arr[-1])


### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])

MOD = 1000000007

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

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

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

print(dp[N])
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

INF = float('inf')

d = [[INF] * W for _ in range(H)]


def bfs(i, j):
    q = deque()
    q.append((i, j))
    d[i][j] = 0

    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and d[nx][ny] > d[x][y] + 1:
                q.append((nx, ny))
                d[nx][ny] = d[x][y] + 1


if H < W:
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                bfs(i, j)

    res = 0
    for i in range(H):
        for j in range(W):
            res = max(res, d[i][j])
else:
    for j in range(W):
        for i in range(H):
            if grid[i][j] == '#':
                bfs(i, j)

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


print(res)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

# d = [[2001] * W for _ in range(H)]


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and grid[nx][ny] != '#':
                res_q.append((nx, ny))
                grid[nx][ny] = '#'
    return res_q


q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            q.append((i, j))

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)
### BUGGY CODE ###

n, k = map(int, input().split())
lis = []
for _ in range(n):
    a, b = map(int, input().split())
    for _ in range(b):
        lis.append(a)
lis.sort()
print(lis[k-1])
        

### FIXED CODE ###

n, k = map(int, input().split())
cnt = [0] * (10**5 + 1)
for _ in range(n):
    a, b = map(int, input().split())
    cnt[a] += b
for i in range(10**5 + 1):
    if k <= cnt[i]:
        ans = i
        break
    else:
        k -= cnt[i]
print(ans)
### BUGGY CODE ###

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

#　ans = 2**n
n2 = n
ans = 1
rou = 0
while n2 >= 1:
    n2, rem = divmod(n2, 2)
    if rem == 1:
        ans *= 2**(2**rou)
    rou += 1

#　数え過ぎたものを引く
def comb(n, r):
    m = 1
    for i in range(n-r+1, n+1):
        m *= i
    for i in range(1, r+1):
        m //= i
    return m
ans -= comb(n, a) + comb(n, b) + 1


print(int(ans % (1000000007)))

### FIXED CODE ###

#TLE

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    return ans

n, a, b = map(int, input().split())
ans = pow(2, n, 10**9+7) - comb_mod(n, a, 10**9+7) - comb_mod(n, b, 10**9+7) - 1
if ans < 0:
    ans += 10**9 + 7
if ans < 0:
    ans += 10**9 + 7

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

n, m = map(int, input().split())
s = input()
for _ in range(m):
    l, r = map(int, input().split())
    tmps = s[l - 1:r]
    print(tmps.count("AC"))


### FIXED CODE ###

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

#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
s = sum(a)
r = [sum(a[:i + 1]) for i in range(n)]
print(min(abs(2 * i - s) for i in r))


### FIXED CODE ###

#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
s = sum(a)
r = [a[0]]
for i in range(1, n):
    r.append(r[i - 1] + a[i])
print(min(abs(2 * i - s) for i in r))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(n, rest):
    global C, N
    rst = 0
    if maxR[n] > 0:
        rst = maxR[n]
    elif rest >= C and S[n] == 'o':
        rst += 1
        if n + (C + 1) < N:
            rst += dfs(n + C + 1, C)
    else:
        if n + 1 < N:
            rst += dfs(n + 1, rest + 1)
    return rst


def dfs2(n, rest):
    global C, N
    rst = 0
    if maxL[n] > 0:
        rst = maxL[n]
    elif rest >= C and S[n] == 'o':
        rst += 1
        if n - (C + 1) >= 0:
            rst += dfs2(n - (C + 1), C)
    else:
        if n - 1 >= 0:
            rst += dfs2(n - 1, rest + 1)
    return rst


N, K, C = map(int, input().split())
S = input()
maxR = [-1] * N
for i in range(N):
    if S[i] == 'o' and maxR[i] == -1:
        maxR[i] = dfs(i, C)

if maxR[-1] == -1:
    maxR[-1] = 0
for i in range(N - 2, -1, -1):
    if maxR[i] == -1:
        maxR[i] = maxR[i + 1]

maxL = [-1] * N
for i in range(N - 1, -1, -1):
    if S[i] == 'o' and maxL[i] == -1:
        maxL[i] = dfs2(i, C)

if maxL[0] == -1:
    maxL[0] = 0
for i in range(1, N):
    if maxL[i] == -1:
        maxL[i] = maxL[i - 1]

ans = []
for i in range(N):
    r = maxR[i + 1] if i + 1 < N else 0
    l = maxL[i - 1] if i - 1 >= 0 else 0
    if r + l < K:
        ans.append(i + 1)

print(*ans, sep='\n')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(n, rest):
    global C, N
    rst = 0
    if maxR[n] > 0:
        rst = maxR[n]
    elif rest >= C and S[n] == 'o':
        rst += 1
        if n + (C + 1) < N:
            rst += dfs(n + C + 1, C)
    else:
        if n + 1 < N:
            rst += dfs(n + 1, rest + 1)
    maxR[n] = rst
    return rst


def dfs2(n, rest):
    global C, N
    rst = 0
    if maxL[n] > 0:
        rst = maxL[n]
    elif rest >= C and S[n] == 'o':
        rst += 1
        if n - (C + 1) >= 0:
            rst += dfs2(n - (C + 1), C)
    else:
        if n - 1 >= 0:
            rst += dfs2(n - 1, rest + 1)
    maxL[n] = rst
    return rst


N, K, C = map(int, input().split())
S = input()
maxR = [-1] * N
for i in range(N):
    if S[i] == 'o' and maxR[i] == -1:
        maxR[i] = dfs(i, C)

if maxR[-1] == -1:
    maxR[-1] = 0
for i in range(N - 2, -1, -1):
    if maxR[i] == -1:
        maxR[i] = maxR[i + 1]

maxL = [-1] * N
for i in range(N - 1, -1, -1):
    if S[i] == 'o' and maxL[i] == -1:
        maxL[i] = dfs2(i, C)

if maxL[0] == -1:
    maxL[0] = 0
for i in range(1, N):
    if maxL[i] == -1:
        maxL[i] = maxL[i - 1]

ans = []
for i in range(N):
    r = maxR[i + 1] if i + 1 < N else 0
    l = maxL[i - 1] if i - 1 >= 0 else 0
    if r + l < K:
        ans.append(i + 1)

print(*ans, sep='\n')
### BUGGY CODE ###

import collections

n = int(input())
a_list = list(map(int, input().split()))
c = collections.Counter(a_list)
for k in range(n):
    c[a_list[k]] -= 1
    ans = 0
    for i in c.values():
        ans += i*(i-1)//2
    print(ans)
    c[a_list[k]] += 1

### FIXED CODE ###

import collections

n = int(input())
a_list = list(map(int, input().split()))
c = collections.Counter(a_list)
ans = 0
for i in c.values():
    ans += i*(i-1)//2
for i in range(n):
    print(ans - (c[a_list[i]]-1))
### BUGGY CODE ###

from sys import stdin
from itertools import accumulate


def main():
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]
    a1 = [A[0]]
    tmp = A[0]
    for i in range(1, N):
        tmp = tmp ^ A[i]
        a1.append(tmp)
    a2 = list(accumulate(A))

    count = 0
    for l in range(N):
        for r in range(l, N):
            s1 = a1[r] ^ (0 if l == 0 else a1[l - 1])
            s2 = a2[r] - (0 if l == 0 else a2[l - 1])
            if (s1 == s2):
                count += 1
            if (s2 > 2 ** 20):
                break
    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin
from itertools import accumulate


def main():
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]
    A1 = [A[0]]
    for i in range(1, N):
        A1.append(A1[-1] ^ A[i])
    A2 = list(accumulate(A))
    l = 0
    r = 1
    tmp1 = A1[0]
    tmp2 = A2[0]
    count = 0
    while True:
        if (l == N - 1) and (r == N):
            count += 1
            break

        if (r != N) and (tmp1 ^ A[r + 1 - 1] == tmp2 + A[r + 1 - 1]):
            if tmp1 == tmp2:
                count += 1
            r += 1
            tmp1 = tmp1 ^ A[r - 1]
            tmp2 = tmp2 + A[r - 1]
            continue
        else:
            if tmp1 == tmp2:
                count += (r - l - 1)
            tmp1 = tmp1 ^ A[l]
            tmp2 = tmp2 - A[l]
            l += 1

    print(count)


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

import numpy as np

def main():
    H,N = map(int, input().split())
    weight = list(); value = list()
    for n in range(N):
        temp = input().split()
        weight.append(int(temp[0]))
        value.append(int(temp[1]))
    
    inf = float("inf")
    dp = np.zeros([N+1, H+max(weight)+1])
    for i in range(N+1):
        for j in range(H+max(weight)+1):
            dp[i,j] = inf
    for i in range(N+1): dp[i,0] = 0
    for i in range(N):
        for h in range(H+max(weight)+1):
            if(weight[i] <= h):
                dp[i+1,h]=min(dp[i,h-weight[i]]+value[i], dp[i+1,h-weight[i]]+value[i], dp[i,h])
            else:
                dp[i+1,h]=dp[i,h]
    res = int(min(dp[N][H:]))
    print(res)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    H,N = map(int, input().split())
    weight = list(); value = list()
    for n in range(N):
        temp = input().split()
        weight.append(int(temp[0]))
        value.append(int(temp[1]))
    
    inf = float("inf")
    dp = [[inf for i in range(H+max(weight)+1)] for j in range(N+1)]
    for i in range(N+1): dp[i][0] = 0
    for i in range(N):
        for h in range(H+max(weight)+1):
            if(weight[i] <= h):
                dp[i+1][h]=min(dp[i][h-weight[i]]+value[i], dp[i+1][h-weight[i]]+value[i], dp[i][h])
            else:
                dp[i+1][h]=dp[i][h]
    res = int(min(dp[N][H:]))
    print(res)



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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math as mt

def main():
    A, B, N = map(int, input().split())

    maxn = 0
    
    if N > B:
        for x in range(B-1, N+1, B):
            temp = mt.floor(A*x/B) - A*mt.floor(x/B)
            if temp >= maxn:
                maxn = temp
            else:
                break
    elif N == B:
        maxn = mt.floor(A*(N-1)/B) - A*mt.floor((N-1)/B)
    else:
        maxn = mt.floor(A*N/B) - A*mt.floor(N/B)
    
    print(maxn)


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math as mt

def main():
    A, B, N = map(int, input().split())

    maxn = 0
    
    if N >= B:
        maxn = mt.floor(A*(B-1)/B) - A*mt.floor((B-1)/B)
    else:
        maxn = mt.floor(A*N/B) - A*mt.floor(N/B)
    
    print(maxn)


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

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N-1):
  for j in range(i+1,N,1):
    ans += A[i]*A[j]
print(ans%(10**9+7))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
tmp = sum(A[1:])
ans = 0
for i in range(N-1):
  ans += A[i]*tmp
  tmp -=A[i+1]
print(ans%(10**9+7))