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

from sys import stdin

N = int(stdin.readline())
L = [int(x) for x in stdin.readline().rstrip().split()]

tmp = 0
for i in range(N):
    for j in range(N-i-1):
        j = j + i + 1
        for k in range(N-j-1):
            k = k + j + 1

            if L[i] < L[j] + L[k]:
                if L[j] < L[i] + L[k]:
                    if L[k] < L[i] + L[j]:
                        tmp = tmp + 1

print(tmp)


### FIXED CODE ###

# 本番では解けず。
from sys import stdin
import bisect

N = int(stdin.readline())
L = [int(x) for x in stdin.readline().rstrip().split()]

# (1)Lを昇順にソートする
L.sort()

s = 0

for i in range(N-2):
    for j in range(i+1, N-1):

        # (2)Lから2つの辺を固定で選ぶ（L[i]をa L[j]をbとする）
        # この場合、a < b + c, b < a + c はソート済みのため自明。
        # c < a + b が成り立つ棒の個数を調べる
        tmp = L[i] + L[j]

        # (3)Lの中から(2)の和(a+b)、を左に挿入できる場所二分探索で探す
        # つまりL[index - 1] < L[i] + L[j] < L[index] になるindexを探す。

        index = bisect.bisect_left(L, tmp)

        # (4) 固定で選んだ大きい方の辺から(3)で見つけた棒の間にある棒の個数を足す
        # b より右にあり、これより左にあるもの　→　開区間　(L[j], L[index])に含まれる棒は c < a + b を満たすので。
        s += (index - (j+1))

print(s)
### BUGGY CODE ###

import math
N = int(input())
def f(n):
    count=0
    for x in range(1,int(math.sqrt(n))):
        for y in range(1,x+1):
            for z in range(1,x+1):
                if x*x+y*y+z*z+x*y+y*z+z*x==n:
                    if x==y and y==z:
                        count+=1
                    else:
                        count=3
    print(count)

for i in range(1,N+1):
    f(i)

### FIXED CODE ###

a=[0]*int(input())
r=range(1,99)
for x in r:
    for y in r:
        for z in r:
            n=x*(x+y+z)+y*(y+z)+z*z-1
            if n<len(a):
                a[n]+=1
print(*a)
### BUGGY CODE ###

A,B,Q = map(int, input().split())
s = [-(10**11)]+[int(input()) for _ in range(A)]+[10**11]
t = [-(10**11)]+[int(input()) for _ in range(B)]+[10**11]
s.sort()
t.sort()

def bi(arr, l, r, val):
    if r-l<=1:
        return l
    m = (l+r)//2
    if val < arr[m]:
        return bi(arr, l, m, val)
    else:
        return bi(arr, m, r, val)

import itertools
for _ in range(Q):
    pos = int(input())
    s_near_id = bi(s, 0, len(s), pos)
    t_near_id = bi(t, 0, len(t), pos)
    print(min( min(abs(pos-s_pos)+abs(s_pos-t_pos), abs(pos-t_pos)+abs(t_pos-s_pos)) for s_pos, t_pos in itertools.product(s[s_near_id:s_near_id+2],t[t_near_id:t_near_id+2]) ))


### FIXED CODE ###

A,B,Q = map(int, input().split())
s = [-(10**11)]+[int(input()) for _ in range(A)]+[10**11]
t = [-(10**11)]+[int(input()) for _ in range(B)]+[10**11]
s.sort()
t.sort()

import bisect
import itertools
for _ in range(Q):
    pos = int(input())
    s_near_id = bisect.bisect_left(s, pos)-1
    t_near_id = bisect.bisect_left(t, pos)-1
    print(min( min(abs(pos-s_pos)+abs(s_pos-t_pos), abs(pos-t_pos)+abs(t_pos-s_pos)) for s_pos, t_pos in itertools.product(s[s_near_id:s_near_id+2],t[t_near_id:t_near_id+2]) ))
### BUGGY CODE ###

from numba import jit
import math
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
S = [0] * N
S[0] = 0
 
@jit
def nya(S, N):
    for i in range(1, N):
        value = math.inf
        for step in range(1, K + 1):
            if i - step < 0:
                break
            value = min(value, S[i - step] + abs(h[i] - h[i - step]))
        S[i] = value
    return S

S = nya(S, N)
print(S[N - 1])

### FIXED CODE ###

from numba import jit
import math
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
@jit
def nya(N, K, h):
    S = [0] * N
    S[0] = 0
 
    for i in range(1, N):
        value = math.inf
        for step in range(1, K + 1):
            if i - step < 0:
                break
            value = min(value, S[i - step] + abs(h[i] - h[i - step]))
        S[i] = value
    return S[N-1]

print(nya(N, K, h))
### BUGGY CODE ###

from itertools import combinations

n = int(input())
s = input()

print(len(set(combinations(s, 3))))

### FIXED CODE ###

n = int(input())
s = list(map(int, input().rstrip()))

ans = 0
for i in range(10):
    if i in s[:n - 2]:
        x = s.index(i)

        for j in range(10):
            if j in s[x + 1:n - 1]:
                y = x + s[x + 1:n - 1].index(j) + 1

                for k in range(10):
                    if k in s[y + 1:]:
                        ans += 1

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

def main():
    n = int(input())
    s = [int(input()) for _ in range(n)]
    s_sum = []
    def dfs(i, sum):
        if i == n:
            s_sum.append(sum)
        else:
            dfs(i + 1, sum + s[i])
            dfs(i + 1, sum)
    dfs(0, 0)
    s_sum_c = [s for s in s_sum if s % 10 != 0]
    s_sum_c.append(0)
    print(max(s_sum_c))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    s = [int(input()) for _ in range(n)]
    s_sum = sum(s)
    s = [i for i in s if i % 10 != 0]
    s.sort()
    if s_sum % 10 != 0:
        print(s_sum)
        exit()
    for es in s:
        if (s_sum - es) % 10 != 0:
            print(s_sum - es)
            exit()
    else:
        print(0)

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

N = int(input())
A = sorted(list(map(int,input().split())))
def gcd(L):
    
    

    while True:
        NL = []
        #print(L)
        minb = min(L)
        for l in L:
            r = l % minb
            if r != 0:
                NL.append(r)
        if(len(NL) == 0):
            return minb
        NL.append(minb)
        L = NL


max = 0
for i in range(1,len(A)+1):
    g = gcd(A[0:i-1]+A[i:])
    #print(i,g,(A[0:i-1]+A[i:]))
    if max < g:
        max = g
print(max)


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
def gcdaaaaaaaaa(L):
    nextminb = L[0]
    nextn = len(L)
    while True:
        n = nextn
        minb = nextminb
        for l in L[:n]:
            nextn = 0
            r= l % minb
            
            if r != 0:
                L[nextn] = r
                nextn += 1
                if r < nextminb :
                    nextminb = r
        if minb == nextminb:
            return minb
        
def gcd(a,b):
    r = a % b
    if r == 0:
        return b
    else:
        return gcd(b,r)
def gcdL(L):
    g = L[0]
    for l in L:
        g = gcd(g,l)
    return g



lgcd = [0] * N
rgcd = [0] * N

lg = A[0]
rg = A[-1]
for i in range(N):
    
    lg = gcd(lg,A[i])
    lgcd[i] = lg
    rg = gcd(rg,A[N-i-1])
    rgcd[N-i-1] = rg
    
maxg = max(lgcd[N-2],rgcd[1])
for i in range(1,N-1):
    g = gcd(lgcd[i-1],rgcd[i+1])
    if maxg < g:
        maxg = g

print(maxg)
### BUGGY CODE ###

import math

def calc_comb(n):
    k = 2
    if n <= 1 :
        return 0
    elif n ==2 :
        return 1
    return math.factorial(n)/(math.factorial(n-k) * math.factorial(k))

n = int(raw_input(""))

smap = {}
tmp = ""
for i in range(0, n):
    tmp = ''.join(sorted(raw_input("")))
    if smap.get(tmp, None) == None:
        smap[tmp] = 1
    else:
        smap[tmp] += 1
count = 0
for s, num in smap.items():
    #print num
    count += calc_comb(num)
print count


### FIXED CODE ###

import math

def calc_comb(n):
    k = 2
    if n <= 1 :
        return 0
    elif n ==2 :
        return 1
    return math.factorial(n)/(math.factorial(n-k) * math.factorial(k))

n = int(raw_input(""))

smap = {}
tmp = ""
for i in range(0, n):
    tmp = ''.join(sorted(raw_input("")))
    if smap.get(tmp, None) == None:
        smap[tmp] = 1
    else:
        smap[tmp] += 1
count = 0
for s, num in smap.items():
    #print num
    count += calc_comb(num)
print count
### BUGGY CODE ###

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

all = 2**n - 1
tmp1 = 1
tmp2 = 1
tmp3 = 1
tmp4 = 1
for i in range(1, a+1):
    tmp1 *= n - i + 1
for i in range(1, a+1):
    tmp2 *= i
for i in range(1, b+1):
    tmp3 *= n - i + 1
for i in range(1, b+1):
    tmp4 *= i
result = all - ((tmp1//tmp2) + (tmp3//tmp4)) 
print(result%(10**9 + 7))

### FIXED CODE ###

n, a, b = [int(i) for i in input().split()]
mod = 10**9 + 7
 
total = pow(2, n, mod) - 1
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
 
at = combination(n,a)
bt = combination(n,b)
 
result = total - at - bt
result %= mod
if result < 0:
  result += mod
print(result)
### BUGGY CODE ###



def main(N,A):
    B=[0]

    for i in range(int(len(A))):
        T = A[i] + B[i]
        B.append(T)
    count = 0
    M=0
    for i in range(int(len(B))):
        for m in range(int(len(B))):
            if i-m < 0:
                continue
            if i > i-m:
                T = B[i]-B[i-m]
                # print(i, m)
                # print(B[i],B[i-m])
                # print(T)
                if T == 0:
                    # print("kore",B[i],B[i-m])
                    count += 1

    #print(count)
    #print(B)
    return print(count)




if __name__ == "__main__":
    N=int(input())
    A=list(map(int,input().split()))
    main(N,A)

### FIXED CODE ###

import collections

def main(N,A):
    B=[0]
    count = 0
    for i in range(N):
        T = A[i] + B[i]

        B.append(T)
    c = collections.Counter(B)

    for i in range(len(c)):
        k, v = c.popitem()
        for z in range(v):
            count += z

    return print(count)

if __name__ == "__main__":
    N=int(input())
    A=list(map(int,input().split()))

    main(N,A)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [[] for _ in range(n)]
eb = [[] for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].append((u,a))
    ea[u].append((v,a))
    eb[v].append((u,b))
    eb[u].append((v,b))


def dijkstra(e,n,s):
    inf = 10**15
    d = [inf]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u]>c+ud:
                d[u] = c + ud
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(ea,n,s)
db = dijkstra(eb,n,t)
res = [0]*n
m = None
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    if m is None:
        m = r
    else:
        m = min(m,r)

    res[i] = m

for i in range(n):
    print(10**15 - res[i])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
n,m,s,t = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    g[u].append((v,(a,b)))
    g[v].append((u,(a,b)))

inf = 10**18
def dijkstra(s, currency):
    d = [inf]*(n+1)
    d[s] = 0

    que = [(d[s],s)]
    heapq.heapify([que])
    while len(que)>0:
        _,v = heapq.heappop(que)
        for u,c in g[v]:
            if d[v]+c[currency]>=d[u]:
                continue
            d[u] = d[v]+c[currency]
            heapq.heappush(que, (d[u], u))
    return d

yen_c = dijkstra(s,0)
snuuk_c = dijkstra(t,1)

res = [0]*n
res[n-1] = yen_c[n] + snuuk_c[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], yen_c[i+1]+snuuk_c[i+1])

for r in res:
    print(10**15-r)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

memo = [[[-1 for k in range(2)] for j in range(D)] for i in range(N)]

def f(digit, current_sum, flag):
    if digit == -1:
        if current_sum % D == 0:
            return 1
        else:
            return 0

    #if memo[digit][current_sum][flag] != -1:
    #    return memo[digit][current_sum][flag]

    ret = 0
    for i in range(10):
        if flag or i < int(K[N-1-digit]):
            if memo[digit-1][(current_sum+i)%D][1] != -1:
                ret += memo[digit-1][(current_sum+i)%D][1]
            else:
                ret += f(digit-1, (current_sum+i)%D, 1)
        elif i == int(K[N-1-digit]):
            if memo[digit-1][(current_sum+i)%D][0] != -1:
                ret += memo[digit-1][(current_sum+i)%D][0]
            else:
                ret += f(digit-1, (current_sum+i)%D, 0)
        
    memo[digit][current_sum][flag] = ret % MOD
    return ret

#substract 0 case
ans = (f(N-1, 0, 0) - 1) % MOD
print(ans)


### FIXED CODE ###

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

dp = [[[0 for k in range(2)] for j in range(D)] for i in range(N+1)]

dp[0][0][0] = 1
for i, n in enumerate(K):
    n = int(n)
    for j in range(D):
        for k in range(2):
            for d in range(10 if k else n+1):
                dp[i+1][(j+d) % D][k or d < n] += dp[i][j][k]
                dp[i+1][(j+d) % D][k or d < n] %= MOD

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

import sys
from collections import deque
def input():return sys.stdin.readline().strip()

def main():
    H, W = map(int, input().split())

    field = "#" * (W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#" * (W+2)

    move = [-1, 1, -(W+2), W+2]
    cost = [-1] * (H+2) * (W+2)

    def dfs(s):
        q = deque()
        enqueue = q.append
        dequeue = q.popleft

        for v in s:
            cost[v] = 0
            enqueue(v)

        while q:
            now = dequeue()
            for dx in move:
                nv = now + dx
                if field[nv] == "." and cost[nv] < 0:
                    cost[nv] = cost[now] + 1
                    enqueue(nv)
    
    starts = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            now = i*(W+2) + j
            if field[now] == "#":
                starts.append(now)
    dfs(starts)

    print(max(cost))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import deque
def input():return sys.stdin.readline().strip()

def main():
    H, W = map(int, input().split())

    field = "#" * (W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#" * (W+2)

    move = [-1, 1, -(W+2), W+2]
    cost = [-1] * (H+2) * (W+2)

    def dfs(s):
        q = deque()
        enqueue = q.append
        dequeue = q.popleft

        for v in s:
            cost[v] = 0
            enqueue(v)

        while q:
            now = dequeue()
            for dx in move:
                nv = now + dx
                if field[nv] == "." and cost[nv] < 0:
                    cost[nv] = cost[now] + 1
                    enqueue(nv)
    
    starts = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            now = i*(W+2) + j
            if field[now] == "#":
                starts.append(now)
    dfs(starts)

    print(max(cost))

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

N = int(input())
Maxi = [0] * N
for i in range(N):
	Ai = int(input())
	for j in range(N):
		if j == i:
			continue
		if Ai > Maxi[j]:
			Maxi[j] = Ai

for i in range(N):
	print(Maxi[i])


### FIXED CODE ###

N = int(input())
Maxi = [0] * N
Ai = []
for i in range(N):
	Ai.append((i, int(input())))

Ai.sort(key = lambda t: t[1], reverse=True)

mi,max = Ai[0]

for i in range(N):
	Maxi[i] = max

Maxi[mi] = Ai[1][1]

for i in range(N):
	print(Maxi[i])
### BUGGY CODE ###

n,m,q=map(int,input().split())

lr=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    li,ri=map(int,input().split())
    lr[li][ri]+=1
    
for i in range(n+1):
    asum=0
    for j in range(n+1):
        asum+=lr[i][j]
        lr[i][j]=asum
            
for i in range(q):
    pi,qi=map(int,input().split())
#    pi-=1
#    qi-=1
    asum=0
    for j in range(pi,qi+1):
#        print("j:",j,"j-1",j-1,"qo:",qi,lr[j][qi]-lr[j][j-1])
        asum+=lr[j][qi]-lr[j][j-1]
    print(asum)


### FIXED CODE ###

n,m,q=map(int,input().split())

lr=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    li,ri=map(int,input().split())
    lr[li][ri]+=1
    
for i in range(n+1):
    asum=0
    for j in range(n+1):
        asum+=lr[i][j]
        lr[i][j]=asum
            
for i in range(q):
    pi,qi=map(int,input().split())
#    pi-=1
#    qi-=1
    asum=0
    for j in range(pi,qi+1):
#        print("j:",j,"j-1",j-1,"qo:",qi,lr[j][qi]-lr[j][j-1])
        asum+=lr[j][qi]-lr[j][j-1]
    print(asum)
### BUGGY CODE ###

inp = input()
inp = input()
 
def mp(nums):
  n = 1
  for num in nums:
    n *=num
  return n
 
limit= mp([10]*18)
num = mp([int(x) for x in inp.split(" ")])
 
if num > limit:
  print(-1)
else:
  print(num)

### FIXED CODE ###

inp = input()
inp = input()
 
def mp(nums):
  if 0 in nums:
    print(0)
    return
  n = 1
  limit = 10**18
  for num in nums:
    n *=num
    if n > limit:
      print(-1)
      return
  print(n)
 
mp([int(x) for x in inp.split(" ")])
### BUGGY CODE ###

from itertools import product
from copy import deepcopy
S = list(input())
x, y = map( int, input().split())
UD = [] #updown
LR = [0] #leftright
X = deepcopy(LR)
t = 0
for w in S:
    if w == 'F':
        X[-1] += 1
    elif t == 0:
        LR = deepcopy(X)
        X = deepcopy(UD)
        X.append(0)
        t = 1
    else:
        UD = deepcopy(X)
        X = deepcopy(LR)
        X.append(0)
        t = 0
if t == 0:
    LR = deepcopy(X)
else:
    UD = deepcopy(X)
x = x - LR.pop(0)
G = 0
H = 0
LLR = len(LR)
LUD = len(UD)
for B in product([-1,1], repeat = LLR):
    Z = 0
    for i in range(LLR):
        Z += LR[i]*B[i]
    if Z == x:
        G = 1

for B in product([-1,1],repeat = LUD):
    Z = 0
    for i in range(LUD):
        Z += UD[i]*B[i]
    if Z == y:
        H = 1
print('Yes' if G == 1 and H == 1 else 'No')

### FIXED CODE ###

S = input()
x, y = map( int, input().split())
c = 0
ver = []
row = []
l = 0
for s in S:
    if s == "F":
        c += 1
    else:
        if l%2 == 0:
            row.append(c)
        else:
            ver.append(c)
        l += 1
        c = 0
if l%2 == 0:
    row.append(c)
else:
    ver.append(c)

x -= row.pop(0)
row.sort( key = None, reverse = True)
ver.sort( key = None, reverse = True)
nx, ny = 0, 0
for a in row:
    if a >= 0:
        if nx <= x:
            nx += a
        else:
            nx -= a
    else:
        if nx > x:
            nx += a
        else:
            nx -= a
for a in ver:
    if a >= 0:
        if ny <= y:
            ny += a
        else:
            ny -= a
    else:
        if ny > y:
            ny += a
        else:
            ny -= a

if x == nx and y == ny:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import defaultdict
N, S = map(int, input().split())
A = tuple(map(int, input().split()))

mod = 998244353
U = 3000

pow2 = [1] * (U + 1)
for i in range(1, U + 1):
    pow2[i] = pow2[i - 1] * 2 % mod

dp = defaultdict(int)
U = 3000*3000
dp[(0, 0)] = 1
for a in A:
    newDP = defaultdict(int)
    for (sm, cnt), v in dp.items():
        # 追加しない
        newDP[(sm, cnt)] += v
        newDP[(sm, cnt)] %= mod
        # 追加する
        if sm+a <= 3000:
            newDP[(sm+a, cnt + 1)] += v
            newDP[(sm+a, cnt + 1)] %= mod
    dp = newDP

ans = 0
for i in range(N + 1):
    ans = (ans + pow2[N - i] * dp[(S, i)]) % mod
print(ans)

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
fft = np.fft.rfft
ifft = np.fft.irfft
mod = 998244353

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

dp = np.zeros(U+10, dtype=np.int64)
dp[0] = 1
for a in A:
    newDP = dp.copy() * 2
    newDP[a:] += dp[:-a]
    newDP %= mod
    dp = newDP

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

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[]
p=0
for i in range((n-k+1)):
    for j in range(k):
        p+=(((a[i+j]*(1+a[i+j]))/2)/a[i+j])
    ans.append(p)
    p=0
print(max(ans))


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
new_p=[]
s=[]
ans=-(10**9)
for i in range(n):
    new_p.append((1+p[i])/2)
s.append(new_p[0])
for i in range(n-1):
    s.append(s[i]+new_p[i+1])
s.insert(0,0)
for i in range((len(s)-k)):
    val=s[k+i]-s[i]
    ans=max(ans,val)
print(ans)
### BUGGY CODE ###

import numpy as np
S = input()

MOD = 10 ** 9 + 7

dp = np.array([[0] * 13] * (len(S) + 1))
dp[0][0] = 1
for i in range(len(S)):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])

    for k in range(10):
        if c == -1 or c == k:
            for j in range(13):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
    dp[i + 1] %= MOD
print(dp[len(S)][5])

### FIXED CODE ###

r = [[(j - k) * 9 % 13 for j in range(10)] for k in range(13)]
d = [1] + [0] * 12
M = 10 ** 9 + 7
for c in input():
    if c == '?':
        d = [sum(d[j] for j in k) % M for k in r]
    else:
        d = [d[(int(c) - k) * 9 % 13] for k in range(13)]
    #print(d)
print(d[5])
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def sumcmb(T):
    count=0
    m=T
    while m>=0:
        count+=cmb(T,m)
        T-=1
        m-=2
        count%=mod

    return(count)


N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
mod=10**9+7
for i in range(M-1):
    if A[i]+1==A[i+1]:
        print(0)
        exit()

if 1 not in A:
    A.insert(0,-1)
if N not in A:
    A.append(N+1)


count=1
for i in range(len(A)-1):
    T=max(A[i+1]-1 - (A[i]+1),1)
    #print(sumcmb(T))
    count*=sumcmb(T)
    count%=mod

print(count)


### FIXED CODE ###

N,M=map(int,input().split())
mod=10**9+7
A=set([int(input()) for i in range(M)])

data=[0 for i in range(N)]
if 1 not in A:
    data[0]=1
if N>=2:
    if 2 not in A:
        data[1]=1+data[0]


for i in range(2,N):
    if i+1 not in A:
        data[i]=data[i-1]+data[i-2]
        data[i]%=mod

#print(data)

print(data[-1])
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n = int(input())
list_ABC = [ list(map(int,input().split(" "))) for i in range(n-1)]
q, k = map(int, input().split())
list_XY = [ list(map(int,input().split(" "))) for i in range(q)]

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1, k-1]+b[k-1, y-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])
### BUGGY CODE ###

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

answer=0

for i in range(1,N+1):
    f=int(A*i/B)-A*int(i/B)
    if f>answer:
        answer=f
    if f<answer:
        break
    #print(f)
print(answer)
        

### FIXED CODE ###

import math
A,B,N=map(int,input().split())

def f(x):
    return int(A*x/B)-A*int(x/B)

print(f(min(N,B-1)))
### BUGGY CODE ###

n,m = map(int,input().split())
lr = [list(map(int,input().split())) for i in range(m)]

wildcard = set(range(lr[0][0],lr[0][1]+1))
for i in range(1,len(lr)):
    wildcard &= set(range(lr[i][0],lr[i][1]+1))

ans = len(wildcard)
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
lr = [list(map(int,input().split())) for i in range(m)]

lp = 1
rp = n

for i in range(m):
    if lp < lr[i][0]:
        lp = lr[i][0]
    if rp > lr[i][1]:
        rp = lr[i][1]
else:
    if rp - lp < 0:
        ans = 0
    else:
        ans = rp-lp+1

print(ans)