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

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

ans = [1] * (N+1)
for L,R in LR:
    ans[:L] = [0] * L
    ans[R+1:] = [0] * (N+1-R)

print(ans.count(1))

### FIXED CODE ###

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

L = []
R = []
for i in range(M):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)

if min(R)-max(L)+1 <= 0:
    print(0)
else:
    print(min(R)-max(L)+1)
### BUGGY CODE ###

from math import gcd

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True
c2 = True

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

hoge = 0
for i in num_lis:
  hoge = gcd(hoge, i)
if hoge > 1:
  print("not coprime")
  exit()

d_lis = osa_k(10**6+10)
tmp = set()
for i in num_lis:
  num = i
  new_tmp = set()
  while num > 1:
    d = d_lis[num]
    new_tmp.add(d)
    num //= d
  if len(tmp | new_tmp) != len(tmp)+len(new_tmp):
    print("setwise coprime")
    exit()
  else:
    tmp |= new_tmp
print("pairwise coprime")


### FIXED CODE ###

from math import gcd
N = int(input())
A = list(map(int,input().split()))

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p,MAXN+1,p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

st = set()
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    for p in tmp:
        if p in st:
            print('setwise coprime')
            exit()
        st.add(p)
print('pairwise coprime')
### BUGGY CODE ###

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

mod = 10**9+7

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

def lcm(a,b):
    return (a*b//gcd(a,b))

now = a[0]
for i in range(1, n):
    now = lcm(max(now, a[i]), min(now, a[i]))
result = 0
for i in range(n):
    result =(result + now // a[i])%mod
print(result)

### FIXED CODE ###

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

mod = 10**9+7
ism = defaultdict(int)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

for i in range( n):
    dl = factorization(a[i])
    for x, y in dl:
        if ism[x] < y:
            ism[x] = y
lcd = 1
for i in ism.keys():
    lcd = (lcd * (i ** ism[i]))%mod
result = 0
for i in range(n):
    result =(result + lcd *extgcd(a[i],mod)[0])%mod
print(result)
### BUGGY CODE ###

a = [ int(i) for i in input().split()]

b = (a[0]*a[1]) % 2019

for i in range (a[0], a[1]):
  for j in range (i+1, a[1]+1):
    b = min (b, (i*j)%2019)
    if b == 0:
      break
    
print(b)      

### FIXED CODE ###

a = [ int(i) for i in input().split()]

b = (a[0]*a[1]) % 2019

for i in range (a[0], a[1]):
  for j in range (i+1, a[1]+1):
    b = min (b, (i*j)%2019)
    
    if b == 0:
      break
      
  if b == 0:
    break
    
print(b)
### BUGGY CODE ###

from collections import deque
import copy

H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = deque([(i, j) for i in range(H) for j in range(W) if a[i][j] == '#'])
count = 0

flag_all = False

while True:
	count += 1

	que_next = deque()
	while que:
		i, j = que.popleft()
		for k in range(4):
			dx, dy = d[k][0], d[k][1]
			x = i + dx
			y = j + dy
			if x >= 0 and x < H and y >= 0 and y < W and a[x][y] != '#':
				a[x][y] = '#'
				que_next.append((x, y))

	que = copy.copy(que_next)

	if que:
		que = copy.copy(que_next)
	else:
		break
print(count-1)


### FIXED CODE ###

from collections import deque
import copy

H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = deque([(i, j) for i in range(H) for j in range(W) if a[i][j] == '#'])
count = 0

flag_all = False

while True:
	count += 1

	que_next = deque()
	while que:
		i, j = que.popleft()
		for k in range(4):
			dx, dy = d[k][0], d[k][1]
			x = i + dx
			y = j + dy
			if x >= 0 and x < H and y >= 0 and y < W and a[x][y] != '#':
				a[x][y] = '#'
				que_next.append((x, y))

	que = copy.copy(que_next)

	if que:
		que = copy.copy(que_next)
	else:
		break
print(count-1)
### BUGGY CODE ###

a,b,c=map(int, input().split(" "))
ans=0
while not a==b==c:
    if (a==b or b==c or c==a):
        if a==b and a<c:
            a += 1
            b += 1
            ans += 1
        elif a==b and a>c:
            c += 2
            ans += 1
        elif a == c and a < b:
            c += 1
            a += 1
            ans += 1
        elif a == c and a > b:
            b += 2
            ans += 1
        elif b == c and a < b:
            a += 2
            ans += 1
        elif b == c and a < b:
            b += 1
            c += 1
            ans += 1
    else:
        if a<b and a<c:
            a+=2
            ans+=1
        elif b<c:
            b+=2
            ans+=1
        else:
            c+=2
            ans+=1
print(ans)

### FIXED CODE ###

a,b,c=map(int, input().split(" "))
ans=0
if (max(a,b,c)*3-a-b-c)%2==0:
    ans=int((max(a,b,c)*3-a-b-c)/2)
else:
    ans = ((max(a, b, c) * 3 - a - b - c) // 2)+2
print(ans)
### BUGGY CODE ###

from collections import Counter


def solve(string):
    n, *uvw = map(int, string.split())
    count = Counter(uvw[::3] + uvw[1::3])
    uvw = list(zip(uvw[::3], uvw[1::3], uvw[2::3]))
    whites = set([count.most_common(1)[0][0]])
    blacks = set([])
    while len(uvw) > 0:
        tmp = []
        for i in range(len(uvw)):
            t = uvw.pop()
            if t[0] in whites:
                if t[2] % 2 == 0:
                    whites.add(t[1])
                else:
                    blacks.add(t[1])
            elif t[1] in whites:
                if t[2] % 2 == 0:
                    whites.add(t[0])
                else:
                    blacks.add(t[0])
            elif t[0] in blacks:
                if t[2] % 2 == 0:
                    blacks.add(t[1])
                else:
                    whites.add(t[1])
            elif t[1] in blacks:
                if t[2] % 2 == 0:
                    blacks.add(t[0])
                else:
                    whites.add(t[0])
            else:
                tmp.append(t)
        uvw = tmp
    ans = ["0"] * n
    for i in range(n):
        if i + 1 in blacks:
            ans[i] = "1"

    return "\n".join(ans)


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))


### FIXED CODE ###

N=int(input());p=[[]for _ in range(N+1)]
for _ in range(N-1):u,v,w=map(int,input().split());p[u].append((v,w));p[v].append((u,w))
s=[(1,0)];l=[-1]*N
while s:
 a,w=s.pop()
 l[a-1]=w%2
 for b,c in p[a]:
  if l[b-1]==-1:s.append((b,w+c))
for i in l:print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

dp={}
dp_up={}
V_max=0

for i in range(1,N+1):
    w,v=map(int,input().split())

    V_max+=v

    for j in range(v,V_max+1):
        if j==v:
            if j in dp:
                dp_up[j]=min(dp[j],w)
                j_max=j
            else:
                dp_up[j]=w
                j_max=j
        else:
            if j-v in dp and dp[j-v]+w<=W:
                if j in dp:
                    dp_up[j]=min(dp[j],dp[j-v]+w)
                    j_max=j
                else:
                    dp_up[j]=dp[j-v]+w
                    j_max=j
    dp=dp_up.copy()
print(max(dp))    

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

dp={}
dp_up={}
V_max=0

for i in range(1,N+1):
    w,v=map(int,input().split())

    V_max+=v

    for j in range(v,V_max+1):
        if j==v:
            if j in dp:
                dp_up[j]=min(dp[j],w)
                j_max=j
            else:
                dp_up[j]=w
                j_max=j
        else:
            if j-v in dp and dp[j-v]+w<=W:
                if j in dp:
                    dp_up[j]=min(dp[j],dp[j-v]+w)
                    j_max=j
                else:
                    dp_up[j]=dp[j-v]+w
                    j_max=j
    dp=dp_up.copy()
print(max(dp))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans=1
for e in a:
  ans *= e
if(ans > 10**18):
  print("-1")
else:
  print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans=1
for e in a:
  ans *= e
  if(ans > 10**18) :
    ans = -1
    break
print(ans)
### BUGGY CODE ###

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

def zal(s):
    i = 1
    j = 0
    _N = len(s)
    Z = [0]*_N
    Z[0] = _N
    res = 0
    while i < _N:
        while i + j < _N and s[j] == s[i+j]:
            j += 1
        Z[i] = j

        if Z[i] <= i:
            res = max(res, Z[i])

        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < _N and k + Z[k] < j:
            Z[i+k] = Z[k]

            if Z[i+k] <= i+k:
                res = max(res, Z[i+k])

            k += 1
        i += k
        j -= k
    return res

ans = 0
for i in range(N):
    _S = S[i:]
    res = zal(_S)
    ans = max(ans, res)
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
 
def zal(s):
    i = 1
    j = 0
    _N = len(s)
    Z = [0]*_N
    Z[0] = _N
    res = 0
    while i < _N:
        while i + j < _N and s[j] == s[i+j]:
            j += 1
        Z[i] = j
 
        if Z[i] <= i:
            res = max(res, Z[i])
 
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < _N and k + Z[k] < j:
            Z[i+k] = Z[k]
 
            if Z[i+k] <= i+k:
                res = max(res, Z[i+k])
 
            k += 1
        i += k
        j -= k
    return res
 
ans = 0
for i in range(N):
    _S = S[i:]
    res = zal(_S)
    ans = max(ans, res)
print(ans)
### BUGGY CODE ###

from collections import deque


def merge(a, l, m, r):
    global cnt
    n1, n2 = m - l, r - m
    ll = deque(a[l + i] for i in range(n1))
    rl = deque(a[m + i] for i in range(n2))
    for k in range(l, r):
        a[k] = (ll if not rl or ll and ll[0] <= rl[0] else rl).popleft()
        cnt += 1


def merge_sort(a, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        merge_sort(a, l, m)
        merge_sort(a, m, r)
        merge(a, l, m, r)


n, a, cnt = int(input()), list(map(int, input().split())), 0
merge_sort(a, 0, n)
print(*a)
print(cnt)

### FIXED CODE ###

from collections import deque

INFTY = 1e9 + 1


def merge(a, l, m, r):
    global cnt
    ll = deque(a[l:m])
    rl = deque(a[m:r])
    ll.append(INFTY)
    rl.append(INFTY)
    for k in range(l, r):
        a[k] = (ll if ll[0] < rl[0] else rl).popleft()
    cnt += r - l


def merge_sort(a, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        merge_sort(a, l, m)
        merge_sort(a, m, r)
        merge(a, l, m, r)


n, a, cnt = int(input()), list(map(int, input().split())), 0
merge_sort(a, 0, n)
print(*a)
print(cnt)
### BUGGY CODE ###

import itertools

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

Q_list = []
for _ in range(Q):
    q = list(map(int, input().split()))
    Q_list.append(q)

A_list = []
for a in itertools.combinations_with_replacement(range(1, M+1), N):
    A_list.append(a)

score_list = []
for A in A_list:
    score = 0
    for i in range(Q):
        a, b, c, d = Q_list[i][0], Q_list[i][1], Q_list[i][2], Q_list[i][3]
        a -=1
        b -=1
        if A[b] - A[a] == c:
            score += d
    score_list.append(score)

print(max(score_list))

### FIXED CODE ###

import itertools

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

Q_list = []
for _ in range(Q):
    a, b, c, d = list(map(int, input().split()))
    Q_list.append((a, b, c, d))

A_list = []
for a in itertools.combinations_with_replacement(range(1, M+1), N):
    A_list.append(a)

answer = 0
score_list = []
for A in A_list:
    score = 0
    for i in range(Q):
        a, b, c, d = Q_list[i]
        a -=1
        b -=1
        if A[b] - A[a] == c:
            score += d
    answer = max(answer, score)

print(answer)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=list(map(int,input().split()))
def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)
for ai in A:
    pro=lcm(pro,ai)
for ai in A:
    count+=pro//ai
    count%=mod
print(count)

### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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


def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)

P = 10**9 + 7
N = 1000010
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

for ai in A:
    pro=lcm(pro,ai)
for ai in A:
    ans+=inv_t[ai]
    ans%=mod
print((pro*ans)%mod)

# pro2=1
# for ai in A:
#     pro2=(pro2*ai)%mod
#     pro=gcd(pro,ai)
# for ai in A:
#     count+=pro//ai
#     count%=mod
# print(count)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

m = [0] * n
for i in range(n-k+1):
  m[i] = sum(p[i:i+k])
print((max(m) + k)/2)


### FIXED CODE ###

import itertools

n, k = list(map(int, input().split()))
p = list(map(int, input().split()))

pa = list(itertools.accumulate([0] + p))

m = 0
for i in range(n-k+1):
  s = pa[i+k] - pa[i]
  if s > m:
    m = s
print((m+k)/2)
### BUGGY CODE ###

import sys
from collections import deque
readline = sys.stdin.readline
n = int(readline())
D = [[-1]*n for _ in range(n)]
for i in  range(n): D[i][i]=0
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c = map(lambda x:int(x)-1, map(int, readline().split()))
    G[a].append(b)
    G[b].append(a)
    D[a][b] = c+1
    D[b][a] = c+1

q, k = map(int, readline().split())
k -= 1
que = deque([k])
_D = [-1]*n
_D[k] = 0
while que:
    nw = que.popleft()
    d = _D[nw]
    for nx in G[nw]:
        if nw!=k and _D[nx]!=-1: continue
        _D[nx] = d+D[nw][nx]
        que.append(nx)

for i in range(q):
    x, y = map(lambda x: int(x)-1, readline().split())
    print(_D[x]+_D[y])

### FIXED CODE ###

import sys
sys.setrecursionlimit(pow(10,6))
readline = sys.stdin.readline

def dfs(nw, d):
    V[nw] = d
    for nx in G[nw]:
        if V[nx[0]]==-1:
            dfs(nx[0], d+nx[1])

n = int(readline())
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c = map(int, readline().split())
    G[a-1].append((b-1,c))
    G[b-1].append((a-1,c))
q, k = map(int, readline().split())

V = [-1]*n
dfs(k-1, 0)

for i in range(q):
    x,y = map(lambda x:int(x)-1, readline().split())
    print(V[x]+V[y])
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[32]:


K = int(input())


# In[33]:


if K%2 == 0 or K%5 == 0:
    print(-1)
else:
    for i in range(1,K+1):
        if int("7"*i)%K == 0:
            print(i)
            break
    else:
        print(-1)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[40]:


K = int(input())


# In[44]:


if K%2 == 0 or K%5 == 0:
    print(-1)
else:
    if K%7 == 0:
        L = 9*K//7
    else:
        L = 9*K
    ans = -1
    tmp = 0
    for i in range(1,K+1):
        if (10*tmp+9)%L == 0:
            ans = i
            break
        else:
            tmp = (10*tmp+9)%L
    print(ans)


# In[ ]:
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit
def solve(N, costX, costY):
    ans = [INF] * (N + 1)

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
            if cost >= ans[M]:
                break
        else:
            ans[M] = cost

    return ans

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: xyp[2], reverse=False)

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]

    def calcCost(AP, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = solve(N, costX, costY)
    print(*ans, sep='\n')

sol()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [float('inf')] * n
dp[0] = 0

for i in range(1, n):
    for j in range(max(i - k, 0), i):
        dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))

print(dp[n - 1])


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

def frog(n, k, h):
    d = [float('inf')] * n
    d[0] = 0

    for i in range(1, n):
        d[i] = min(
            d[j] + abs(h[i] - h[j]) for j in range(max(i - k, 0), i)
        )
    return d[n - 1]


print(frog(n, k, h))
### BUGGY CODE ###

n,m = map(int, input().split())
a = 1
for i in range(m):
    a *= n
    if a > 1000000007:
        a %= 1000000007
print(a)

### FIXED CODE ###

def power(n,m):
    if m == 0:
        return 1
    if m % 2 == 0:
        return power(n*n%1000000007,m//2)
    else:
        return n * power(n,m-1) % 1000000007
        
n,m = map(int, input().split())
print(power(n,m))
### BUGGY CODE ###

mod = 10**9+7

NN = 10**4 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Map = [[] for _ in range(N+1)]
for n in range(1, N+1):
    a = 1
    for _ in range(N+1):
        Map[n].append(a)
        a = a * g2[n] % mod

L = [[] for _ in range(N+1)]
for n in range(A, B+1):
    for c in range(C, D+1):
        if n*c > N:
            continue
        L[n].append(c)

dp = [0]*(N+1)
dp[0] = 1
for n in range(1, N+1):
    for i, c in enumerate(L[n]):
        if i == 0:
            dp2 = dp[:]
        for nn in range(N+1-n*c):
            dp2[nn+n*c] = (dp2[nn+n*c] + dp[nn] * Map[n][c] % mod * Map[c][1] % mod) % mod
        if i == len(L[n])-1:
            dp = dp2

ans = dp[N] * g1[N] % mod
print(ans)


### FIXED CODE ###

mod = 10**9+7

NN = 10**4 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Map = [[] for _ in range(N+1)]
for n in range(1, N+1):
    a = 1
    for _ in range(N+1):
        Map[n].append(a)
        a = a * g2[n] % mod

L = [[] for _ in range(N+1)]
for n in range(A, B+1):
    for c in range(C, D+1):
        if n*c > N:
            continue
        L[n].append(c)

dp = [0]*(N+1)
dp[0] = 1
for n in range(1, N+1):
    for i, c in enumerate(L[n]):
        if i == 0:
            dp2 = dp[:]
        for nn in range(N+1-n*c):
            dp2[nn+n*c] = (dp2[nn+n*c] + dp[nn] * Map[n][c] % mod * Map[c][1] % mod) % mod
        if i == len(L[n])-1:
            dp = dp2

ans = dp[N] * g1[N] % mod
print(ans)
### BUGGY CODE ###

from functools import reduce
from operator import mul
import sys

input = sys.stdin.readline

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

j = 1000000000000000000
ans = 1
ans = reduce(mul, An)


if ans > j :
    print(-1)
    
else :
    print(ans)



### FIXED CODE ###


n = int(input())
An = [int(x) for x in input().split()]
An.sort(reverse=True)

if 0 in An:
    print(0)
    exit()

j = 10 ** 18
ans = 1
for i in range(n):
    if ans > j:
        print(-1)
        quit()
    ans *= An[i]

if ans > j :
    print(-1)
    
else :
    print(ans)
### BUGGY CODE ###

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

for i in range(1, N):
  print(A.count(i))
print(0)

### FIXED CODE ###

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

l = Counter(A)
for i in range(1, N+1):
  print(l[i])