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

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

d = [0]*(N-1)
for i in range(N-1):
    d[i] = x[i+1]-x[i]

kaijou = 1
for i in range(1,N):
    kaijou *= i

ans=0
x=0
for i in range(N-1):
    x+= (kaijou//(i+1))%(10**9+7)
    d[i] %= 10**9+7
    ans+= d[i]*x

print(ans%(10**9+7))

### FIXED CODE ###

import math
import sys 
input = sys.stdin.readline

N = int(input())
x = list(map(int,input().split()))
mod = 10**9+7

d = [0]*(N-1)

for i in range(N-1):
    d[i] = x[i+1]-x[i]
    d[i] %= mod


kaijou = 1
for i in range(1,N):
    kaijou *= i
    kaijou %= mod


ans=0
x=0

def pow_r(x, n):
    """
    O(log n)
    """
    x %= mod
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)%mod
    else:  # standard case ② n is odd
        return (x * (pow_r(x ** 2, (n - 1) // 2)))%mod

for i in range(N-1):
    #(i+1)%(mod-2)を計算してyへ
    y = pow_r(i+1,mod-2)
    #x+= kaijou//(i+1))%(10**9+7)
    x += kaijou*y
    ans += d[i]*x
    ans %= mod

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


#n:
#m:
#k:
n,m,k=map(int,input().split())
friend={}
block={}
result=[]
for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)

for _ in range(m):
    a,b=map(int,input().split())
    friend[a].add(b)
    friend[b].add(a)

for _ in range(k):
    a,b=map(int,input().split())
    block[a].add(b)
    block[b].add(a)


checked=set([])
bfbf=[]
for i in range(1,n+1):
    #print(i,checked)
    if i not in checked:
        checked.add(i)
        group=[i]
        bf=[i]
        while len(group)!= 0:
            temp=group.pop(0)
            for item in friend[temp]:
                if item not in checked:
                    checked.add(item)
                    group.append(item)
                    bf.append(item)
        lenbf=len(bf)
        for item1 in bf:
            bl=0
            for item2 in bf:
                if item2 in block[item1]:
                    bl+=1
            result[item1-1]=lenbf-1-len(list(friend[item1]))-bl



        bfbf.append(bf)
result=list(map(str,result))
print(" ".join(result))







### FIXED CODE ###

#n:
#m:
#k:
n,m,k=map(int,input().split())
friend={}
block={}
result=[]
friendGroup=[]
for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)
    friendGroup.append(0)

for _ in range(m):
    a,b=map(int,input().split())
    friend[a].add(b)
    friend[b].add(a)

checked=set([])
bfbf=[]
for i in range(1,n+1):
    #print(i,checked)
    if i not in checked:
        checked.add(i)
        group=set([i])
        bf=set([i])
        friendGroup[i-1]=i
        while len(group)!= 0:
            temp=group.pop()
            for item in friend[temp]:
                if item not in checked:
                    checked.add(item)
                    group.add(item)
                    bf.add(item)
                    friendGroup[item-1]=i
        lenbf=len(bf)
        for item1 in bf:
            result[item1-1]=lenbf-1-len(list(friend[item1]))

for _ in range(k):
    a,b=map(int,input().split())
    if friendGroup[a-1]!=0 and friendGroup[a-1]==friendGroup[b-1]:
        result[a-1]-=1
        result[b-1]-=1

result=list(map(str,result))
print(" ".join(result))
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
# n=10**5
# a=[i for i in range(2,10**5+2)]
# print(len(a))
a.sort()
tmp=Counter(a)
p=[]
while 1:
    if len(a)==0:
        break
    prime=a[0]
    if tmp[prime]!=1:
        a.pop(0)
        continue
    p.append(prime)
    i=0
    while i <len(a):
        if a[i]%prime==0:
            a.pop(i)
            continue
        i+=1
    # print(a)
    # print(p)
for i in a:
    p.append(i)
print(len(p))
# def eratosthenes(limit):
#     A = [i for i in range(2, limit+1)]
#     # A=a[:]
#     P = []
#     time = 0
#     while True:
#         prime = min(A)
#         if prime > math.sqrt(limit):
#             break  
#         P.append(prime)   
#         i = 0
#         while i < len(A):
#             if A[i] % prime == 0:
#                 A.pop(i)
#                 continue
#             i += 1    
#     for a in A:
#         P.append(a)    
#     return len(P)
# print(a)
# tmp=Counter(a)
# lst=[]
# for i in range(n):
#     if tmp[a[i]]!=1:
#         continue
#     for j in lst:
#         if a[i]%j==0:
#             break
#     else:
#         lst.append(a[i])
# print(len(lst))
# print(eratosthenes(10**5+10))

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

a.sort()
dic=dict(Counter(a))

ans=0
for i in range(n):
    if dic[a[i]]==1:
        ans+=1
    if dic[a[i]]==0:
        continue
    dic[a[i]]=0
    j=1
    while 1:
        j+=1
        if j*a[i]>10**6+10:
            break
        if j*a[i] in dic:
            dic[j*a[i]]=0

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

import heapq
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
a=list(map(int,input().split()))
heapq.heapify(a)

for i in range(m):
    b,c=map(int,input().split())
    for j in range(b):
        temp=heapq.heappop(a)
        if temp<c:
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,temp)
            break
print(sum(a))

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
bc=[list(map(int,input().split())) for i in range(m)]
bc=sorted(bc,reverse=True,key=lambda x:x[1])
c=[]

cnt=0
for B,C in bc:
    for i in range(B):
        if cnt==n:break
        cnt+=1
        c.append(C)
c=sorted(c,reverse=True)

ans=sum(a)
temp=ans
for i in range(n):
    if cnt<=i:continue
    temp+=-a[i]+c[i]
    if temp>ans:ans=temp
print(ans)
### BUGGY CODE ###

n = int(raw_input())
data = map(int, raw_input().split())
m = int(raw_input())
test = map(int, raw_input().split())

def solve(i,left):
    if left == 0:
        return True
    elif i >= n:
        return False
    return solve(i+1, left) or solve(i+1, left - data[i])

for j in range(m):
    if solve(0, test[j]):
        print 'yes'
    else:
        print 'no'

    

### FIXED CODE ###

n = int(raw_input())
data = map(int, raw_input().split())
m = int(raw_input())
test = map(int, raw_input().split())

# def solve(i,left):
#     if left == 0:
#         return True
#     elif i >= n:
#         return False
#     return solve(i+1, left) or solve(i+1, left - data[i])

# for j in range(m):
#     if solve(0, test[j]):
#         print 'yes'
#     else:
#         print 'no'

a = [0]
for i in range(n):
    a = a + [a[j] + data[i] for j in range(len(a))]

for i in range(m):
    if test[i] in a:
        print 'yes'
    else:
        print 'no'
### BUGGY CODE ###

n, a ,b = map(int, input().split())
ans = 0
length = 0
while length <= n:
  length += a + b
  ans += a
over = length - n
if (over == 0):
  print(ans)
else:
  if (over <= b):
    print(ans)
  else:
    over -= b
    ans -= over
    print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
q = n // (a+b)
mod = n % (a+b)
ans = q * a
if (mod > a):
  ans += a
else:
  ans += mod
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 16:49:00 2020

@author: matsui
"""

   
def cost(h,N,K):
    dp=[0]*N
    for i in range(1,N):
        tmp=[]
        for j in range(1,K+1):
            if i-j < 0 : break
            tmp.append(abs(h[i]-h[i-j])+dp[i-j])
        dp[i]=min(tmp)
    return dp[-1]

N,K=map(int,input().split())
h=[int(num) for num in input().split()]

print(cost(h,N,K))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 16:49:00 2020

@author: matsui
"""



N,K=map(int,input().split())
h=[int(num) for num in input().split()]

dp=[0]*N
dp[1]=abs(h[0]-h[1])
   
def cost(h,N,K,dp):
    for i in range(2,N):
        dp[i]=min([abs(h[i]-h[j])+dp[j] for j in range(max(0, i-K), i)])
    return dp[-1]
    
print(cost(h,N,K,dp))
### BUGGY CODE ###

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

def lv(n):
    if n == 0:
        yield 'P'
    else:
        yield 'B'
        for q in lv(n-1):
            yield q
        yield 'P'
        for q in lv(n-1):
            yield q
        yield 'B'

k = 0
i = 0
for n in lv(N):
    #print(n)
    if n == 'P':
        i += 1
    
    k += 1
    
    if k >= X:
        break

print(i)

### FIXED CODE ###

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

a, p = [1], [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
    
def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    
    elif X <= 1 + a[N-1]:
        return f(N-1, X-1)

    else:
        return p[N-1] + 1 + f(N-1, X-2-a[N-1])

print(f(N, X))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split())) 
a = tuple(a)
if a.count(1) == 0:
    print(-1)
else:
    y = n
    s = 0
    for i in range(1, n+1):
        if a[s:].count(i) == 0:
            y = i-1
            break
        else:
            s = a[s:].index(i)+1
    print(n-y)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split())) 
a = tuple(a)
if a.count(1) == 0:
    print(-1)
else:
    s = 0
    t = 1
    for i in range(n):
        if a[i] == t:
            t += 1
        else: s += 1
    print(s)
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
S = list(str(input()))
S.reverse()
extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        for x in range(10):
            each_extras[cnt][x] = x * 10 ** i % 13
        cnt += 1

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for each in each_extras[i]:
        for j in range(13):
            dp[i+1][(j + each) % 13] += dp[i][j] % mod

print(dp[-1][5] % mod)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))


"""
S.reverse()
extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        each_extras[cnt] = []
        for x in range(10):
            each_extras[cnt].append(x * 10 ** i % 13)
            # each_extras[cnt][x * 10 ** i % 13] = 1
        cnt += 1

# print(each_extras)

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for extras in each_extras[i]:
        for j in range(13):
            dp[i+1][(extras + j)%13] += dp[i][j]
            dp[i+1][(extras + j)%13] %= mod
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % mod


# print(dp)
print(dp[-1][5] % mod)
"""


S = list(str(input()))

dp = [[0 for i in range(13)]for j in range(len(S)+1)]
dp[0][0] = 1
S.reverse()
mul = 1
for i in range(len(S)):
    if S[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(mul*j+k)%13] += dp[i][k]
                dp[i+1][(mul*j+k)%13] %= mod
    else:
        for k in range(13):
            dp[i+1][(int(S[i])*mul+k)%13] += dp[i][k]
            dp[i+1][(int(S[i])*mul+k)%13] %= mod
    mul *= 10
    mul %= 13

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

# https://atcoder.jp/contests/abc110/tasks/abc110_d


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


def get_prime_dic(n):
    dic = {}

    i = 2
    while i <= n:
        while n % i == 0:
            n //= i
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        i += 1
    return dic


# Calculate count of combination
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b


def main():

    d = get_prime_dic(M)
    # print(d)

    ans = 1

    for k, v in d.items():
        ans *= combination(v + N - 1, v)
        ans %= 1000000007


    print(ans)

main()


### FIXED CODE ###

N, M = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
def func(M):
  res = []
  i = 2
  while i * i <= M:
    c=0
    while M % i == 0:
      M /= i
      c += 1
    if c > 0:
      res.append(c)
    i += 1
  if M > 1:
    res.append(1)
  return res

def conb(n, r):
  N, R = n, r
  for i in range(1, r):
    N *= n-i
    R *= r-i
  return N // R

res = func(M)
ans = 1
for i in res:
  ans = (ans * conb(i+N-1, i)) % mod
print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
sN = [input() for _ in range(N)]
# counts = [Counter(s) for s in sN]
# pool = []
# ans = 0
# for count in counts:
#     if count in pool:
#         ans += 1
#     else:
#         pool.append(count)
# print(pool)
# # print(get_unique_list(counts))
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if set(sN[i]) == set(sN[j]):
            if Counter(sN[i]) == Counter(sN[j]):
                ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter
from scipy.misc import comb
N = int(input())
s = [''.join(sorted(input())) for _ in range(N)]
ans = 0
for count in Counter(s).values():
    ans += comb(count, 2, exact=True)
print(ans)
### BUGGY CODE ###

n,x=map(int,input().split());a=list(map(int,input().split()));ans=0
for i in range(n-1):
  while sum(a[i:i+1+1])>x:
    if a[i+1]==0:a[i]-=1
    else:a[i+1]-=1
    ans+=1
print(ans)

### FIXED CODE ###

n,x=map(int,input().split());a=list(map(int,input().split()));ans=0
for i in range(n-1):
  m=a[i]+a[i+1]
  if a[i]>=x:a[i+1]=0;a[i]=x
  else:a[i+1]=min(x-a[i],a[i+1])
  ans+=m-a[i]-a[i+1]
print(ans)
### BUGGY CODE ###

N=int(input())
ans = [0 for _ in range(10001)]
for i in range(1001):
  for j in range(1001):
    for k in range(1001):
      v = i*i + j*j + k*k + i*j + j*k + k*i
      if v < 10001:
        ans[v] += 1

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

### FIXED CODE ###

n=int(input())
ans = [0 for _ in range(10001)]
for i in range(1, 101):
  for j in range(1, 101):
    for k in range(1, 101):
      v = i*i + j*j + k*k + i*j + j*k + k*i
      if v < 10001:
        ans[v] += 1

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

# =map(int,input().split())
n,m=map(int,input().split())
a =[list(map(int,input().split())) for i in range(n)]
ans=[]
# print(a)
for i in range(n):
    for k in range(a[i][1]):
        ans.append(a[i][0])
# print(ans)
ans=[int(i) for i in ans]
# print(ans)
ans.sort()
print(ans[m-1])

### FIXED CODE ###

# =map(int,input().split())
n,m=map(int,input().split())
a =[list(map(int,input().split())) for i in range(n)]
a.sort()
import sys
# ans=dict(a)
# print(a)
cnt=0
for i in range(n):
    z=cnt+a[i][1]
    if z>=m:
        print(a[i][0])
        sys.exit()
    else:
        cnt=z

# print(a)
# for i in range(n):
#     for k in range(a[i][1]):
#         ans.append(a[i][0])
# print(ans)
# ans=[int(i) for i in ans]
# print(ans)
# print(ans[m-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

S = list(reversed(list(input().strip())))
P = [list(reversed(v)) for v in ["dream", "dreamer", "erase", "eraser"]]

sys.setrecursionlimit(10000)
def dfs(n):
    if len(S[n:]) == 0:
        return True
    
    for v in P:
        if S[n:n+len(v)] == v:
            if dfs(n + len(v)):
                return True
    
    return False

if dfs(0):
    print("YES")
else:
    print("NO")


### FIXED CODE ###

import sys
input = sys.stdin.readline

S = list(reversed(input().strip()))
P = [list(reversed(v)) for v in ["dream", "dreamer", "erase", "eraser"]]

n = 0
while n < len(S):
    if S[n:n+5] == P[0] or S[n:n+5] == P[2]:
        n += 5
    elif S[n:n+7] == P[1]:
        n += 7
    elif S[n:n+6] == P[3]:
        n += 6
    else:
        print("NO")
        exit()
        
print("YES")
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
DP = [0]
for i in range(N-1):
    act = float("inf")
    for k in range(K):
        if i-k < 0 : break
        act = min(DP[-1-k] + abs(h[i-k]-h[i+1]) , act)
    DP += [act]
 
print(DP[-1])


### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [100000000000 for _ in range(n)]
dp[0] = 0
for i in range(n):
    for j in range(min(i+1,k+1)):
        dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[-1])
### BUGGY CODE ###

import sys
from collections import defaultdict, deque

input = sys.stdin.readline

def chmax(a, b):
    if a > b:
        return a
    else:
        return b

def main():
    N, W = map(int, input().split())
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [0] * (W + 1)


    for _ in range(N):
        w, v = map(int, input().split())
        for sum_w in range(W, w-1, -1):
            dp[sum_w] = chmax(dp[sum_w], dp[sum_w - w] + v)
    print(dp[-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict, deque

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [0] * (W + 1)


    for _ in range(N):
        w, v = map(int, input().split())
        for sum_w in range(W, w-1, -1):
            tv = dp[sum_w - w] + v
            if tv > dp[sum_w]:
                dp[sum_w] = tv
    print(dp[-1])

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

n = int(input())
csf = [list(map(int,input().split())) for _ in range(n-1)]

for i in range(n):
    res = 0
    for t in range(i,n-1):
        c,s,f = csf[t]
        if res<=s:
            res = s + c
        else:
            while res>s:
                s += f
            res = s + c
        #print(i,res)
    print(res)

### FIXED CODE ###

import math

n = int(input())
csf = [list(map(int,input().split())) for _ in range(n-1)]

for i in range(n):
    res = 0
    for t in range(i,n-1):
        c,s,f = csf[t]
        if res<=s:
            res = s + c
        else:
            s += f*math.ceil((res-s)/f)
            res = s + c
        #print(i,res)
    print(res)
### BUGGY CODE ###

s=input()
t=input()

dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
ans=[[['',0,0] for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i,c in enumerate(s):
    for j,d in enumerate(t):
        if c==d:
            dp[i+1][j+1]=dp[i][j]+1
            ans[i+1][j+1]=[c,i,j]
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
            ans[i+1][j+1]=ans[i][j+1] if dp[i+1][j+1]==dp[i][j+1] else ans[i+1][j]

i=len(s)
j=len(t)
s=[]
while i>0 and j>0:
    c,i,j=ans[i][j]
    s.append(c)

print(''.join(s[::-1]))


### FIXED CODE ###

s=input()
t=input()

dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
ans=[[(-1,-1) for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i,c in enumerate(s):
    for j,d in enumerate(t):
        if c==d:
            dp[i+1][j+1]=dp[i][j]+1
            ans[i+1][j+1]=(i,j)
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
            ans[i+1][j+1]=ans[i][j+1] if dp[i+1][j+1]==dp[i][j+1] else ans[i+1][j]

i=len(s)
j=len(t)
ss=['']*dp[i][j]
l=dp[i][j]-1
while i>0 and j>0:
    i,j=ans[i][j]
    if i>-1:
        ss[l]=s[i]
        l-=1

print(''.join(ss))
### BUGGY CODE ###

import collections
import math
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
total = 0

for n in c.items():
  if n[1] > 1:
    total += math.factorial(n[1]) // (math.factorial(n[1]-2) * 2)

for i in range(N):
  ans = total
  ans -= A.count(A[i])-1
  print(ans)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
total = 1

for n in c.items():
  total += n[1]*(n[1]-1)//2

for i in range(N):
  print(total-c[A[i]])
### BUGGY CODE ###

N = int(input())
an = list(map(int, input().split()))
sum = 0
for k in range(len(an) - 1):
    i = k
    for i in range(len(an) - k - 1):
        sum += (an[k] * an[k + i + 1])
        if sum >= (10 ** 9 + 7):
            sum %= (10 ** 9 + 7)
print(sum)

### FIXED CODE ###

p = (10 ** 9 + 7) * 2
N = int(input())
A = [int(x) for x in input().split()]
A2 = [(x ** 2) % p for x in A]
result = (((sum(A) % p) ** 2 - sum(A2) % p) % p) / 2
print(int(result))
### BUGGY CODE ###

def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n)%p
  b=factorial(k)%p
  c=factorial(n-k)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,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
h,w,a,b=map(int,input().split())
mod=10**9+7
if h-a<w-b:
  h,w=w,h
  a,b=b,a
t=0
for i in range(w-b):
  t+=comb(h-a+b-1,b+i,mod)*comb(w-b+a-1,a+i,mod)
print(t%mod)

### FIXED CODE ###

n=200000
mod=10**9+7
def pf(x,y,p):
  if y==0: return 1
  if y%2==0:
    d=pf(x,y//2,p)
    return d*d%p
  if y%2==1:
    return (x*pf(x,y-1,p))%p
facl=[1]
for i in range(1,n+2):
  facl.append(facl[i-1]*i%mod)
invl=[1]*(n+2)
for i in range(1,n+2):
  invl[i]=pf(facl[i],mod-2,mod)
def comb(x,k):
  if x<0 or k<0 or x<k: return 0
  if x==0 or k==0: return 1
  return (facl[x]*invl[k]*invl[x-k])%mod
h,w,a,b=map(int,input().split())
if h-a<w-b:
  h,w=w,h
  a,b=b,a
t=0
for i in range(w-b):
  t+=comb(h-a+b-1,b+i)*comb(w-b+a-1,a+i)
print(t%mod)
### BUGGY CODE ###

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
f=0
for i in range(len(a)):
    if a[i]+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if i in a:
            dp[i]=0
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
  

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)


f=0
for i in range(al-1):
    if a[i+1]==a[i]+1:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
### BUGGY CODE ###

N, K = map(int, input().split())
S = set()

MOD = 998244353
for _ in range(K):
    L, R = map(int, input().split())
    S |= set(range(L, R + 1))
# print(f'{S=}')

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

for i in range(1, len(DP)):
    for s in S:
        if i - s > 0:
            DP[i] += DP[i - s]
    DP[i] %= MOD
# print(f'{DP=}')
print(DP[-1])


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353
LR = []
for _ in range(K):
    L, R = map(int, input().split())
    LR.append((L, R))
# print(f'{LR=}')

DP = [0] * (N + 1)
DP[1] = 1
S = [0] * (N + 1)

for i in range(1, len(DP)):
    for L, R in LR:
        v = S[max(i - L, 0)] - S[max(i - R - 1, 0)]
        DP[i] += v
    DP[i] %= MOD
    S[i] = (S[i - 1] + DP[i]) % MOD

# print(f'{DP=}')
# print(f'{S=}')
print(DP[-1])