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

n=int(input())
mod=10**9+7
ans=0
temp1=1
temp2=1
temp3=pow(2,n,mod)
for i in range(n-1):
    ans+=(((temp1*temp2)%mod)*(temp3%mod-2))%mod
    temp1=((temp1*(n-i))*pow(i+1,mod-2,mod))%mod
    temp2=(temp2*8)%mod
    temp3=pow(2,n-i-1,mod)
    
 
print(ans%mod)

### FIXED CODE ###

n=int(input())
mod=10**9+7
ans=0
temp1=1
temp2=1
temp3=pow(2,n,mod)
for i in range(n-1):
    ans+=(((temp1*temp2)%mod)*(temp3%mod-2))%mod
    temp1=((temp1*(n-i))*pow(i+1,mod-2,mod))%mod
    temp2=(temp2*8)%mod
    temp3=pow(2,n-i-1,mod)
    

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

k=int(input())
mal=1      
n=list(map(int,input().split()))
      
          
for i in range(0,len(n)):
            mal=mal*n[i]
            
if(mal<=10**18):
    print(mal)
else:
    print(-1)


### FIXED CODE ###

k=int(input())
mal=1      
n=list(map(int,input().split()))
      
          
for i in range(0,len(n)):
    mal=mal*n[i]
    if(mal>10**18):
            mal=-1
            break
for j in range(0,len(n)):
    if(n[j]==0):
        mal=0
print(mal)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    while queue:
        y, x = queue.popleft()
        for j in range(-2, 3):
            for k in range(-2, 3):
                new_y, new_x = y + j, x + k
                if 0 <= new_y < H and 0 <= new_x < W:
                    if maze[new_y][new_x] == "." and j * \
                            k == 0 and abs(j) != 2 and abs(k) != 2 and visited[y][x] < visited[new_y][new_x]:
                        visited[new_y][new_x] = visited[y][x]
                        queue.appendleft([new_y, new_x])
                    elif maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2],
              [0, -2], [-1, 2], [-1, 1], [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)

    print(dist if dist != inf else -1)


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

x, y  =input().split(' ')
count = 0
for i in range(int(x)+1):
    for j in range(int(x)+1):
        for k in range(int(x)+1):
            if i + j + k == int(y):
                count += 1

print(count)

### FIXED CODE ###

k, s = map(int, input().split(' '))
count = 0
for i in range(k+1):
    for j in range(k+1):
        if i + j <= s and s<=k+i+j:
            count += 1

print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

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

from itertools import combinations

l.sort()
ans = 0
combs = set(combinations(l,3))

for c in combs:
    if c[0]+c[1]>c[2] and c[1]+c[2]>c[0] and c[2]+c[0]>c[1]:
        ans += 1

print(ans)

### FIXED CODE ###

"""二分探索"""

import sys
sys.setrecursionlimit(10**6)

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

L.sort()
ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        l = j; r = n
        while l+1 < r:
            c = (l+r)//2
            if L[c] < L[i]+L[j]:
                l = c
            else:
                r = c
        ans += l-j
        
print(ans)
### BUGGY CODE ###

N, Q = [int(x) for x in input().split()]
S = input()
res = []
for i in range(Q):
    l, r = [int(x) for x in input().split()]
    res.append(S[l-1:r].count('AC'))
for r in res:
    print(r)


### FIXED CODE ###

N, Q = [int(x) for x in input().split()]
S = input()
R = [0]
res = 0
ans = []
for i in range(N - 1):
    if S[i:i+2] == 'AC':
        res += 1
    R.append(res)
for i in range(Q):
    l, r = [int(x) for x in input().split()]
    ans.append(R[r-1] - R[l-1])
for r in ans:
    print(r)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
s_li = input().split()
num = list(map(int, s_li))

product = 1

for i in range(n):
    product = product * num[i-1]

if product > 10**18:
    print("-1")
else:
    print(product)


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

product = 1

if 0 in a_li:
    product = 0
else:
    for i in a_li:
        product *= i
        if product > 10**18:
            print(-1)
            exit()

print(product)
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(a, b+1):
    if i-a+1 <= k or b-i+1 <= k:
        print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
ans = []
for i in range(a, a+k):
    ans += [i]*(i<=b)
for i in range(b, b-k, -1):
    ans += [i]*(a<=i)
print(*(sorted(set(ans))), sep='\n')
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
saidai = 0
for i in range(n-k+1):
    wa = 0
    for j in range(i, i+k):
        wa += p[j]
    if wa > saidai:
        saidai = wa
kitai = (1/2)*(k+saidai)
print(str(kitai))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
saidai = 0
wa =[None]*n
wa_2 = 0
gokei = 0
for i in range(n):
    gokei += p[i]
    wa[i] = gokei
saidai = wa[k-1]
for j in range(n-k):
    wa_2 = wa[j+k]-wa[j]
    if wa_2 > saidai:
        saidai = wa_2
kitai = (1/2)*(k+saidai)
print(str(kitai))
### BUGGY CODE ###

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

max_num = 0
j = 0
j_max = M + 1
A_sums=[0]
B_sums=[0]
for i in range(N):
    A_sums.append(A_sums[i]+A[i])
for i in range(M):
    B_sums.append(B_sums[i]+B[i])


for i in range(N + 1):
    j = 0
    if A_sums[i]>K:
        break
    while j < j_max:
        if A_sums[i] + B_sums[j] > K:
            j_max = j
            break

        max_num = max(max_num, i + j)
        j += 1
print(max_num)


### FIXED CODE ###

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

max_num = 0
j = 0
j_max = M
A_sums=[0]
B_sums=[0]
for i in range(N):
    A_sums.append(A_sums[i]+A[i])
for i in range(M):
    B_sums.append(B_sums[i]+B[i])


for i in range(N + 1):
    j = 0
    if A_sums[i]>K:
        break
    while A_sums[i]+B_sums[j_max] > K:
        j_max -=1

    max_num = max(max_num, i + j_max)
print(max_num)
### BUGGY CODE ###

# W分の配列を用意、全Wに対してVが最大になるものを見つける
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for _ in range(N)]

dp=[-1]*(W+1)
dp[0]=0
for w,v in WV:
  for i in range(W-w,-1,-1):
    if dp[i]!=-1:
      dp[i+w]=max(dp[i+w],dp[i]+v)
print(max(dp))

### FIXED CODE ###

import numpy as np
n,w=map(int,input().split())
WV=[list(map(int,input().split())) for _ in range(n)]

dp=np.zeros(w+1,int)
for i in range(n):
  w,v=WV[i]
  dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])
### BUGGY CODE ###

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

now = a[0]
idx = 0
gabbege = a[idx]
length = 1
for i in range(1, n):
    if length < k:
        length += 1
        now *= a[i]
    else:
        if now < now // gabbege * a[i]:
            print("Yes")
        else:
            print("No")
        now = now // gabbege * a[i]
        idx += 1
        gabbege = a[idx]

### FIXED CODE ###

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

now = a[0]
idx = 0
gabbege = a[idx]
length = 1
for i in range(1, n):
    if length < k:
        length += 1
        now += a[i]
    else:
        if now < now - gabbege + a[i]:
            print("Yes")
        else:
            print("No")
        now = now - gabbege + a[i]
        idx += 1
        gabbege = a[idx]
### BUGGY CODE ###

def main():
	import itertools
	n,m = map(int,input().split())
	l = [list(map(int,input().split())) for i in range(m)]
	# print(n,m)
	# print(l)
	ans = 0
	ans_pre = 0

	for ID in range(1,n+1):
		# print("---ID = {}---".format(ID))
		ans_pre = 0
		for i in range(m):
			# print("-i = {}-".format(i))
			li = l[i][0]
			# print("li = {}".format(li))
			ri = l[i][1]
			# print("ri = {}".format(ri))
			if ID >= li and ID <= ri:
				ans_pre += 1
			# print("ans_pre = {}".format(ans_pre))
		if ans_pre == m:
			ans += 1
	print(ans)
	




if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	import itertools
	n,m = map(int,input().split())
	l = [list(map(int,input().split())) for i in range(m)]
	gaterange = []
	#gate1とgate2の共通部分を出す
	li = []
	ri = []
	for i in range(m):
		li.append(l[i][0])
		ri.append(l[i][1])
	print(len(list(range(max(li)-1,min(ri)))))
	




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

# 初期入力
import sys
#input = sys.stdin.readline  #文字列では使わない
#S =input().strip()
*S, = input() 
count =0
flag =1
while len(S) >=2 and flag==1:
    flag =0
    l =len(S)
    for i in range(l -1):
        if S[i:i+2] ==["1","0"] or S[i:i+2] ==["0","1"]:
            #print(S[i:i+2])
            del S[i:i+2]
            #print(S,end=" ")
            count +=2
            flag =1
            #break
    #print()
print(count)

### FIXED CODE ###

#計算でもとまるのか・・・
# 初期入力
import sys
#input = sys.stdin.readline  #文字列では使わない
#*S, = input() 
S =input().strip()
c1 =S.count("1")
c0 =S.count("0")
print(min(c0,c1)*2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def main():
    K = int(input())

    x = 7
    first = True
    flag = False
    while True:
        if(first):
            x = 7
            first = False
        else:
            x = x * 10 + 7
        
        if(x % K == 0):
            print(len(str(x)))
            flag = True
            break
    
    if(flag != True):
        print(-1)


if __name__ == "__main__":
    main()
    


### FIXED CODE ###

# -*- coding: utf-8 -*-

def main():
    K = int(input())

    if( K % 2 == 0 or K % 5 == 0):
        print(-1)
        return        

    x = 7
    first = True
    flag = False
    for i in range(1000000):
        if(first):
            x = 7
            first = False
        else:
            #x = (x * 10) + 7
            x = (x * 10)%K + 7%K
        
        if(x % K == 0):
            print(i+1)
            flag = True
            break
    
    if(flag != True):
        print(-1)


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

H,W=map(int,input().split())
S=[input() for _ in range(H)]
ans=float("inf")
def search(i,j,count):
    global ans
    if i==H-1 and j==W-1:
        ans=min(ans,count)
        
    counti=count
    countj=count

    if j<W-1:
        if S[i][j]=="." and S[i][j+1]=="#":
            countj+=1
        search(i,j+1,countj)
    if i<H-1:
        if S[i][j]=="." and S[i+1][j]=="#":
            counti+=1
        search(i+1,j,counti)
search(0,0,1*(S[0][0]=="#"))
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
S=[input() for _ in range(H)]
ans=float("inf")

counter=[[999]*W for _ in range(H)]

def search(i,j,count):
    global ans

    if counter[i][j]!=999:
        ans=min(ans,count+counter[i][j])
        return(counter[i][j])

    dist=999

    if i==H-1 and j==W-1:
        ans=min(ans,count)
        return 0
    countj=count
    counti=count
    
    if j<W-1:
        if S[i][j]=="." and S[i][j+1]=="#":
            countj+=1
        dist=search(i,j+1,countj) + (S[i][j]=="." and S[i][j+1]=="#")
    if i<H-1:
        if S[i][j]=="." and S[i+1][j]=="#":
            counti+=1
        dist=min(dist,search(i+1,j,counti)+(S[i][j]=="." and S[i+1][j]=="#"))
    
    counter[i][j]=dist
    return dist
search(0,0,(S[0][0]=="#")*1)
print(ans)
### BUGGY CODE ###

import sys

K = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
M = int(10**9 + 7)

fact = [1]
for i in range(1, K + len(S) + 10):
    fact.append(fact[-1] * i % M)

finv = [pow(fact[-1], M - 2, M)]
for i in range(K + len(S) + 9, 0, -1):
    finv.append(finv[-1] * i % M)
finv.reverse()

def comb(a, b, m):
    return fact[a] * finv[b] % m * finv[a - b] % m

def hcomb(a, b, m):
    return comb(a + b - 1, a - 1, m)

ans = 0
for l in range(0, K + 1):
    ans += pow(26, l, M) * pow(25, K - l, M) % M * hcomb(len(S), K - l, M) % M
    ans %= M
print(ans)

### FIXED CODE ###

K = int(input())
S = input()
M = int(10 ** 9 + 7)

fact = [1]
for i in range(1, K + len(S) + 10):
    fact.append(fact[-1] * i % M)

finv = [pow(fact[-1], M - 2, M)]
for i in range(K + len(S) + 9, 0, -1):
    finv.append(finv[-1] * i % M)
finv.reverse()

def comb(a, b, m):
    return fact[a] * finv[b] % m * finv[a - b] % m

def hcomb(a, b, m):
    return comb(a + b - 1, a - 1, m)

ans = 0
for l in range(0, K + 1):
    ans += pow(26, l, M) * pow(25, K - l, M) % M * hcomb(len(S), K - l, M) % M
    ans %= M
print(ans)
### BUGGY CODE ###

from collections import deque

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

def exists(length):
    que = deque()
    V = set()
    T = S[:length]
    que.append(T)
    for s in S[length:]:
        if len(que) >= length:
            V.add(que.popleft())
        T = T[1:] + s
        if T in V:
            return True
        que.append(T)
    return False

for i in range(1, N + 1)[::-1]:
    if exists(i):
        print(i)
        exit()

print(0)


### FIXED CODE ###

from collections import deque

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

def isOk(leng):
    hashList = set()
    que = deque([])
    for left in range(N - leng + 1):
        hs = hash(S[left: left + leng])
        if hs in hashList:
            return True
        que.append(hs)
        if len(que) >= leng:
            hashList.add(que.popleft())
    return False

ok = 0
ng = N

while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

q = int(input())

query = [list(map(int, input().split())) for _ in range(q)]

color = [0] * n

def dfs(node, dist, dist_max, col, pre_node):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    if dist == dist_max:
        return
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist+1, dist_max, col, node)

for v, d, c in query[::-1]:
    v -= 1
    dfs(v, 0, d, c, -1)

for co in color:
    print(co)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

q = int(input())

query = [list(map(int, input().split())) for _ in range(q)]

color = [0] * n
depth = [-1] * n

def dfs(node, dist, col, pre_node):
    if dist <= depth[node]:
        return
    depth[node] = dist
    if color[node] == 0:
        color[node] = col
    if dist == 0:
        return
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist-1, col, node)

for v, d, c in query[::-1]:
    v -= 1
    dfs(v, d, c, -1)

for co in color:
    print(co)
### BUGGY CODE ###

from math import sqrt
from heapq import heappush, heappop

INF = float('inf')

# 単一始点最短経路を求める（ダイクストラ法）
def Dijkstra(adjList, vSt):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))

    while PQ:
        c, vNow = heappop(PQ)
        if c > costs[vNow]: continue

        numUsed += 1
        if numUsed == numV: break

        costNow = c
        for v2, wt in adjList[vNow]:
            c2 = costNow + wt
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))

    return costs


xs, ys, xt, yt = map(int, input().split())
N = int(input())
barriers = [(xs, ys, 0), (xt, yt, 0)] + [tuple(map(int, input().split())) for _ in range(N)]

adjL = [[] for v in range(N + 2)]
for i in range(N + 2):
    xi, yi, ri = barriers[i]
    for j in range(i + 1, N + 2):
        xj, yj, rj = barriers[j]
        wt = max(0, sqrt((xj - xi) ** 2 + (yj - yi) ** 2) - ri - rj)
        adjL[i].append((j, wt))
        adjL[j].append((i, wt))

costs = Dijkstra(adjL, 0)
print(costs[1])


### FIXED CODE ###

from math import sqrt
from heapq import heappush, heappop

INF = float('inf')

# 単一始点最短経路を求める（ダイクストラ法）
def Dijkstra(barriers, vSt):
    numV = len(barriers)
    rests = set(range(numV))
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))

    while PQ:
        c, vNow = heappop(PQ)
        if c > costs[vNow]: continue

        rests.remove(vNow)
        if not rests: break

        costNow = c
        xi, yi, ri = barriers[vNow]
        for v2 in rests:
            xj, yj, rj = barriers[v2]
            wt = sqrt((xj - xi) ** 2 + (yj - yi) ** 2) - ri - rj
            if wt < 0: wt = 0
            c2 = costNow + wt
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))

    return costs


xs, ys, xt, yt = map(int, input().split())
N = int(input())
barriers = [(xs, ys, 0), (xt, yt, 0)] + [tuple(map(int, input().split())) for _ in range(N)]

costs = Dijkstra(barriers, 0)
print(costs[1])
### BUGGY CODE ###

# coding: utf-8
# Your code here!

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
n = int(input()) #n:頂点数　w:辺の数

d = [[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n-1):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
# print(warshall_floyd(d))

dist = warshall_floyd(d)

for elm in dist[0]:
    if elm % 2 == 0:
        print(0)
    else:
        print(1)

### FIXED CODE ###

# coding: utf-8
# Your code here!

def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
        
  return dist
        
n = int(input()) #n:頂点数　w:辺の数

# d = [[float("inf") for i in range(n)] for i in range(n)] 
d = []
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n-1):
    # x,y,z = map(int,input().split())
    # x -= 1
    # y -= 1
    # d[x][y] = z
    # d[y][x] = z
    d.append(list(map(int,input().split())))
# for i in range(n):
#     d[i][i] = 0 #自身のところに行くコストは０
# print(warshall_floyd(d))

dist = BFS(0,d,n)
# print(dist)
for elm in dist:
    if elm % 2 == 0:
        print(0)
    else:
        print(1)
### BUGGY CODE ###

# coding: utf-8
import sys
import itertools


def sr(): return sys.stdin.readline().rstrip()


def ir(): return int(sr())


def lr(): return list(map(int, sr().split()))


N, M = lr()
l_list = []
r_list = []
for i in range(M):
    l, r = lr()
    l_list.append(l)
    r_list.append(r)

ans = set()
for i in range(M):
    cards = sorted(l_list[i:] + r_list[:i + 1])
    cards = set(range(cards[0], cards[-1] + 1, 1))
    if (len(ans) == 0):
        ans = cards
        continue

    ans = cards & ans

print(len(ans))


### FIXED CODE ###

# coding: utf-8
import sys
import itertools


def sr(): return sys.stdin.readline().rstrip()


def ir(): return int(sr())


def lr(): return list(map(int, sr().split()))


N, M = lr()
l_list = []
r_list = []
for i in range(M):
    l, r = lr()
    l_list.append(l)
    r_list.append(r)

# ans = set()
# left = l_list[M - 1]
# right = r_list[0]
tl_list = []
tr_list = []
for i in range(M):
    tmp_left = l_list[i]
    tmp_right = r_list[i]
    tl_list.append(tmp_left)
    tr_list.append(tmp_right)
left = max(tl_list)
right = min(tr_list)
# cards = sorted(l_list[i:] + r_list[:i + 1])
# cards = set(range(cards[0], cards[-1] + 1, 1))
# if (len(ans) == 0):
#     ans = cards
#     continue

# ans = cards & ans

ans = right - left + 1
if ans <= 0:
    print(0)
else:
    print(ans)
### BUGGY CODE ###

import math

def Is(x):
  flag = False
  i = 2
  while i<math.sqrt(x):
    if x%i==0:
      flag = True
      break
      i+=1
  return flag

a = int(input())
ans = 0
flag2 = True
i = 0
while flag2:
  flag2 = Is(a+i)
  ans = a+i
  i+=1

print(ans)

### FIXED CODE ###

import math

def Is(x):
  flag = False
  i = 2
  while i < math.sqrt(x):
    if x % i==0:
      flag = True
      break
    i += 1
  return flag

a = int(input())
ans = 0
flag2 = True
i = 0
while flag2:
  flag2 = Is( a + i )
  ans = a + i
  i += 1

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

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
for i in range(m):
    a.sort(reverse = True)
    a[0] //= 2
print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)  # aを優先度付きキューに

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(a))
### BUGGY CODE ###

N, K, *H = map(int, open(0).read().split())
H.extend([float('inf')] * K)
dp = [float('inf')] * (N + K)
dp[0] = 0
for i, hi in enumerate(H[1:], 1):
    dp[i] = min(dp[i - k] + abs(H[i - k] - hi) for k in range(1, K + 1))
print(dp[N - 1])

### FIXED CODE ###

N, K, *H = map(int, open(0).read().split())
H.extend([float('inf')] * K)
dp = [float('inf')] * (N + K)
dp[0] = 0
for i, hi in enumerate(H[1:], 1):
    dp[i] = min(dp[i - k] + abs(H[i - k] - hi) for k in range(1, K + 1))
print(dp[N - 1])
### BUGGY CODE ###

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

answerList = []

for i in range(N[0]):
    for j in range(N[0] + 1):
        if j > i > 0:
            calculateList = [abs(j - i),
                             abs(N[1] - i) + 1 + abs(j - N[2]),
                             abs(N[2] - i) + 1 + abs(j - N[1])]
            answerList.append(min(calculateList))

for i in range(N[0] - 1):
    print(answerList.count(i + 1))

### FIXED CODE ###

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

answerList = []

for i in range(N[0]):
    answerList.append(0)

for i in range(N[0]):
    if i > 0:
        for j in range(N[0]):
            if j + 1 > i > 0:
                calculateList = [abs(j + 1 - i),
                                 abs(N[1] - i) + 1 + abs(j + 1 - N[2]),
                                 abs(N[2] - i) + 1 + abs(j + 1 - N[1])]
                answer = min(calculateList)
                answerList[answer] = answerList[answer] + 1

for i in range(N[0] - 1):
    print(answerList[i + 1])