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

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def use_divisors(n):
    l_divisors, r_divisors = [], []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if (n//i)%2:
                l_divisors.append(i)
            if i != n//i:
                if (n//(n//i))%2:
                    r_divisors.append(n//i)
    return l_divisors + r_divisors[::-1]

N = I()
X = str(input())

ans = 0
divisors = use_divisors(2*N)

C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = ''.join('1' if c=='0' else '0' for c in T)
    Tc = T+Tr
    count = int(T,2)
    if int(Tc*(N//d)+Tc[:N-d*(N//d)],2) <= int(X,2):
        count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

ans = 0
for d in divisors:
    ans += d*C[d]
    ans %= mod

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def use_divisors(n):
    l_divisors, r_divisors = [], []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if (n//i)%2:
                l_divisors.append(i)
            if i != n//i:
                if (n//(n//i))%2:
                    r_divisors.append(n//i)
    return l_divisors + r_divisors[::-1]
 
N = I()
X = str(input())
Xr = ''.join('1' if c=='0' else '0' for c in X)

ans = 0
divisors = use_divisors(2*N)
C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = Xr[:d//2]
    Tc = T+Tr
    count = int(T,2)
    if int(Tc*(N//d)+Tc[:N-d*(N//d)],2) <= int(X,2):
        count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

ans = 0
for d in divisors:
    ans += d*C[d]
    ans %= mod

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

N,K = map(int,input().split())
p = list(map(int,input().split()))

ans = 0
ans_list = list()
for i in range(N-K+1):
	ex = sum(p[i:i+K])
	if ans < ex:	
		ans = ex
		ans_list = p[i:i+K]

ans_ex = 0
for i in range(K):
	ans_ex += sum(range(1,ans_list[i]+1))/ans_list[i]
print(ans_ex)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))

# 期待値の累積和リストを生成
ex_list = list() 
for i in range(len(p)):
	if i != 0:
		ex_list.append(((1+p[i])/2)+ex_list[-1])
	else:
		ex_list.append((1+p[i])/2)

ans = ex_list[K-1]
for i in range(N-K):
	# print(i,ex_list[i],ex_list[i+K])
	ex = abs(ex_list[i] - ex_list[i+K])
	if ans < ex:
		ans = ex
print(ans)
### BUGGY CODE ###

from bisect import bisect_left


def count_inversion(A):
    cnt = 0
    L = len(A)
    for i in reversed(range(L - 1)):
        j = bisect_left(A, A[i], i + 1, L)
        cnt += j - i - 1
        tmp = A[i]
        del A[i]
        A.insert(j - 1, tmp)
    return cnt


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    print(count_inversion(A))


main()



### FIXED CODE ###

#! /usr/local/bin/python3
# coding: utf-8

from math import inf

inv = 0


def merge(A, left, mid, right):
    global inv

    L = A[left:mid]
    L.append(inf)
    R = A[mid:right]
    R.append(inf)
    i = j = 0
    for k in range(left, right):
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            inv += len(L) - i - 1
            A[k] = R[j]
            j += 1


def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    merge_sort(A, 0, n)
    print(inv)


main()
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                ans += 1
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k+1):
    for y in range(k+1):
        if 0 <= s - x - y <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

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

dp = [10 ** 8 + 1 for i in range(h + 10 ** 4 + 1)]
dp[0] = 0

for i in range(h+1):
  if dp[i] == 10 ** 8 + 1:
      continue
  for a, b in l:
    x = dp[i] + b
    if dp[i + a] > x:
      dp[i + a] = x

print(min(dp[h:]))


### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()
### BUGGY CODE ###

import sys
s= sys.stdin.readline().rstrip() 
t= sys.stdin.readline() .rstrip()
Ns=len(s)
Nt=len(t)
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
for i in range(1,Ns+1):
    for j in range(1,Nt+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]
print(dp[Ns][Nt])

### FIXED CODE ###

S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###

ignore = int(raw_input())
k = map(int, raw_input().split())
copyk = list(set(k))
counter = 0


for i in xrange(len(copyk)):
    while(k.count(copyk[i]) > copyk[i]):
        k.remove(copyk[i])
        counter += 1
    if k.count(copyk[i]) < copyk[i]:
        while(copyk[i] in k):
            k.remove(copyk[i])
            counter += 1


print counter


### FIXED CODE ###

from collections import Counter

ignore = int(raw_input())
k = dict(Counter(map(int, raw_input().split())))
copyk = list(set(k))
counter = 0
for i,j in k.items():
    if i > j:
        counter += j
    elif i < j:
        counter += j - i

print counter
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    pw = str(i).zfill(3)
    idx = 0
    for c in s:
        if c == pw[idx]: idx += 1
        if idx == 3:
            ans += 1
            break
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
cnt = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            idx = 0
            a = S.find(str(k),idx)
            if a != -1:
                idx = a
                b = S.find(str(j),idx+1)
                if b != -1:
                    idx = b
                    c = S.find(str(i),idx+1)
                    if c != -1:
                        cnt += 1

print(cnt)
### BUGGY CODE ###

def f(a, b, x):
    return int(a * x / b) - a * int(x / b)


num = list(map(int, input().split()))
a = num[0]
b = num[1]
n = num[2]
x = 1
max_num = 0
while x % b != 0 and x <= n:
    new_num = f(a, b, x)
    if max_num < new_num:
        max_num = new_num
    x += 1
print(max_num)


### FIXED CODE ###

def f(a, b, x):
    return int(a * x / b) - a * int(x / b)


num = list(map(int, input().split()))
a = num[0]
b = num[1]
n = num[2]
x = (int(n/b) + 1) * b - 1
max_num = f(a, b, min(b-1, n))
print(max_num)
### BUGGY CODE ###

N, M = map(int,input().split( ))
l = []
for i in range(M):
	a,b = map(int,input().split( ))
	l.append([a, b])

ans = 'IMPOSSIBLE'
for i in range(M):
	if l[i][0] == 1:
		t = l[i][1]
		for j in range(M):
			if l[j][0] == t and l[j][1] == N:
				ans = 'POSSIBLE'
print(ans)

### FIXED CODE ###

N, M = map(int,input().split( ))
l = []
for i in range(M):
	a,b = map(int,input().split( ))
	l.append([a, b])

t_a = []
t_b = []

ans = 'IMPOSSIBLE'
for i in range(M):
	if l[i][0] == 1:
		t_a.append(l[i][1])
	elif l[i][1] == N:
		t_b.append(l[i][0])
t_and = set(t_a) & set(t_b)
t_and_l = list(t_and)
if len(t_and_l) > 0:
	ans = 'POSSIBLE'
print(ans)
### BUGGY CODE ###

from fractions import Fraction
n = int(input())
nums = [list(map(int,input().split())) for _ in range(n)]
a, b = nums[0][0], nums[0][1]
for i in range(1, n):
    if a / nums[i][0] != b / nums[i][1]:
        p, q = nums[i][0], nums[i][1]
        while p < a or q < b:
            p += nums[i][0]
            q += nums[i][1]
        a, b = p, q
        
print(a + b)

### FIXED CODE ###

from math import ceil
from fractions import Fraction
n = int(input())
nums = [list(map(int,input().split())) for _ in range(n)]
a, b = 1, 1
p = 1
for i in range(n):
    x, y = nums[i][0], nums[i][1]
    p = ceil(max(Fraction(a, x), Fraction(b, y)))
    a, b = p * x, p * y
        
print(a + b)
### BUGGY CODE ###

import numpy as np
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    matrix=np.zeros((60,1))
    for i in range(n-1,-1,-1):
        ne=np.array([(a[i]>>j)&1 for j in range(60)])
        matrix=np.c_[matrix,ne]
        col=matrix.shape[1]
        ra=np.linalg.matrix_rank(matrix)
        if s[i]=="0":
            if col!=ra+1:
                matrix=np.delete(matrix,col-1,1)
        else:
            if col==ra+1:
                print(1)
                break
    else:
        print(0)

### FIXED CODE ###

#一次独立：rankが成分数
import numpy as np
#0-indexed,MSBがma以下の時
def msb(x,ma=59):
    for i in range(ma,-1,-1):
        if (x>>i)&1:
            return i
    return len()
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    #独立、msb同じものはない
    #逆に異なれば独立
    msbs=[0 for i in range(60)]
    for i in range(n-1,-1,-1):
        now=a[i]
        m=59
        #独立のときfはTrue、独立でない時fはFalse
        while True:
            m=msb(now,m)
            if msbs[m]==0:
                f=True
                break
            now=msbs[m]^now
            if now==0:
                f=False
                break
        if s[i]=="0":
            if f:
                msbs[m]=now
        else:
            if f:
                print(1)
                break
    else:
        print(0)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N,K=LI()
INL=LI()
DP=[False]*(K+1)

for i in range(0,K+1):
    for v in INL:
        if v+i <= K:
            DP[v+i] = DP[v+i] or not DP[i]

# print(DP)
print('First' if DP[K] else 'Second')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N,K=LI()
INL=LI()
DP=[False]*(K+1)

for i in range(0,K+1):
    for v in INL:
        if v+i <= K:
            DP[v+i] = DP[v+i] or not DP[i]

# print(DP)
print('First' if DP[K] else 'Second')
### BUGGY CODE ###

n,a = map(int,input().split())
x = [int(i) for i in input().split()]

sum_x = sum(x)

dp = [[[0 for i in range(n+1)]for j in range(sum_x+1)]for k in range(n+1)]

dp[0][0][0] = 1

for i in range(n):
    for j in range(n):
        for k in range(sum_x+1):
            dp[i+1][k][j] += dp[i][k][j]
            if k + x[i] > sum_x:
                continue
            dp[i+1][k+x[i]][j+1] += dp[i][k][j]
            
ans = 0

for i in range(n):
    if a*(i+1) > sum_x:
        break
    ans += dp[n][a*(i+1)][i+1]

print(ans)

### FIXED CODE ###

n,a = map(int,input().split())
x = [int(i) for i in input().split()]

sum_x = sum(x)

dp = [[[0 for i in range(n+1)]for j in range(sum_x+1)]for k in range(n+1)]

dp[0][0][0] = 1

for i in range(n):
    for j in range(n):
        for k in range(sum_x+1):
            dp[i+1][k][j] += dp[i][k][j]
            if k + x[i] > sum_x:
                continue
            dp[i+1][k+x[i]][j+1] += dp[i][k][j]
            
ans = 0

for i in range(n):
    if a*(i+1) > sum_x:
        break
    ans += dp[n][a*(i+1)][i+1]

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

from operator import mul
from functools import reduce

X,Y = map(int,input().split()[:2])

if (X + Y) % 3 != 0:
    print(0)
    exit()

x_tmp=X
y_tmp=Y

x_count=0
y_count=0

while x_tmp*2 != y_tmp:
    x_tmp-=2
    y_tmp-=1
    x_count+=1

y_count = y_tmp//2

sum = x_count + y_count

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

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

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

ret = cmb(N,x_count,mod)
print(ret)


### FIXED CODE ###

from operator import mul
from functools import reduce

X,Y = map(int,input().split()[:2])

if (X + Y) % 3 or not (X <= 2*Y and Y <= 2*X):
    print(0)
    exit()

x_tmp=X+1
y_tmp=Y+2

x_count=0
y_count=0

while x_tmp*2 != y_tmp:
    x_tmp-=2
    y_tmp-=1
    x_count+=1

y_count = y_tmp//2 - 1

sum = x_count + y_count

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

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

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

ret = cmb(sum,x_count,mod)
print(ret)
### BUGGY CODE ###

import sys
N,M = map(int, input().split())
tmax = int(M/N)
t = tmax
while 1 == 1:
  if M%t==0:
    print(t)
    sys.exit()
  t += -1

### FIXED CODE ###

import sys
import math
N,M = map(int, input().split())
if N==1:
  print(M)
  sys.exit()
tmax = int(M/N)
t = tmax
divisor_list = [1]
for i in range(2, int(math.sqrt(M)) + 1):
  if M % i == 0:
    divisor_list.append(i)
    divisor_list.append(M//i)
divisor_list.sort(reverse = True)
for nums in divisor_list:
  if nums <= tmax:
    print(nums)
    sys.exit()
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)] 
      
for _ in range(M):
    a,b = map(int,input().split())
    fr[a].append(b)
    fr[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    bl[c].append(d)
    bl[d].append(c)

fl = [-1 for i in range(N+1)]
fl[0] = 0
fl[1] = 1
nxt = 1
dic = {}
while nxt != 0:
    q = collections.deque([nxt])
    
    fl[nxt]=nxt
    cnt = 0
    while q:
        now = q.popleft()
        for f in fr[now]:
            if fl[f] == -1:
                fl[f] = nxt
                cnt +=1
                q.append(f)
    dic[nxt] = cnt
    if -1 in fl:
        nxt = fl.index(-1)
    else:
        nxt = 0

mbf = collections.deque()
for i in range(1,N+1):
    ff = 0
    for j in bl[i]:
        if fl[j] == fl[i]:
            ff -= 1
    
    ff += dic[fl[i]]-len(fr[i])
    mbf.append(ff)
print(*mbf)


### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)]

          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s.discard(now)
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        #try:
            #nxt = fl.index(-1)
        #except:
            #nxt = 0
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()


    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

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

N,M = map(int,input().split())
lis  = [list(map(int,input().split())) for _ in range(M)]
ans_lis = [0] * M
lis_sort = sorted(lis)
i = 1
flag = 0
for _ in lis_sort:
    if flag != _[0]:
        flag = _[0]
        i = 1
    ans_lis[lis.index(_)] = str(i)
    i += 1
for x,y in zip(lis,ans_lis):
    print('0'*(6-len(str(x[0]))),x[0],'0'*(6-len(y)),y,sep='')



### FIXED CODE ###

N,M = map(int,input().split())
lis  = [list(map(int,input().split())) for _ in range(M)]
ans_lis = [0] * M
lis_sort = sorted(lis,key =lambda x:(x[0],x[1]))
flag = lis_sort[0][0]
i = 1
for x in lis_sort:
    if x[0] != flag:
        flag = x[0]
        i=1
    x[1] = '0'*(6-len(str(i)))+str(i)
    i+=1
for x in lis:
    print('0'*(6-len(str(x[0]))),str(x[0]),x[1],sep='')
### BUGGY CODE ###

N,K = map(int, input().split())
l = list(map(int,input().split()))
 
def E(n):
  return sum(range(1,n+1)) / n
 
m = 0
if N == 1:
  l2 = list(map(E, l))
  print(sum(l2))
elif N == K:
  l2 = list(map(E, l))  
  print(sum(l2))
else:
  j = sum(l[0:0+K])
  for i in range(1,len(l)-(K-1)):
      j = j - l[i-1] + l[i+K-1]
      if l[i] < l[i-1]:
          continue
      elif m < j:
          m = j
          t = l[i:i+K]

  l2 = list(map(E, t))
 
  print(sum(l2))

### FIXED CODE ###

N,K = map(int, input().split())
l = list(map(int,input().split()))
 
def E(n):
  return (1 + n) / 2
 
j = sum(l[0:0+K])
m = 0
if N == 1:
  l2 = list(map(E, l))
  print(sum(l2))
elif N == K:
  l2 = list(map(E, l))  
  print(sum(l2))
else:
  for i in range(1,len(l)-(K-1)):
      j = j - l[i-1] + l[i+K-1]
      if l[i] < l[i-1]:
          continue
      elif m < j:
          m = j
          t = l[i:i+K]

  l2 = list(map(E, t))
 
  print(sum(l2))
### BUGGY CODE ###

N = int(input())

p = 2
counter = 0
while N != 1:
 ind = 0
 n = -1
 while N % p == 0:
  N //= p
  ind += 1
 if ind == 0:
  p += 1
  continue
 while (n+1)*(n+2)//2 <= ind:
  n += 1
 counter += n
 p += 1

print(counter)

### FIXED CODE ###

import math

N = int(input())

p = 2
counter = 0
while N != 1:
 if p > math.sqrt(N):
  counter += 1
  break
 ind = 0
 n = -1
 while N % p == 0:
  N //= p
  ind += 1
 if ind == 0:
  p += 1
  continue
 while (n+1)*(n+2)//2 <= ind:
  n += 1
 counter += n
 p += 1

print(counter)
### BUGGY CODE ###

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

def factorial(n):
    val = 1
    for i in range(2, n + 1):
        val *= i
    return val

if abs(n-m)>1:
    print(0)
elif abs(n-m)==1:
    print(factorial(n)*factorial(m)%mod)
else:
    print(factorial(n)*factorial(m)*2%mod)


### FIXED CODE ###

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

def factorial(n):
    val = 1
    for i in range(2, n + 1):
        val *= i
        val %= mod
    return val

if abs(n-m)>1:
    print(0)
elif abs(n-m)==1:
    num = factorial(min(m,n))
    print(num**2*max(m,n)%mod)
else:
    num = factorial(m)
    print(num**2*2%mod)
### BUGGY CODE ###

N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

i = 0
while 1:
    if P[0][2] > 0:
        break
    i += 1
x0, y0, h0 = P[i]
for cy in range(101):
    for cx in range(101):
        h = h0 + abs(cx - x0) + abs(cy - y0)
        for x, y, h1 in P:
            if h1 != max(h - abs(cx - x) - abs(cy - y), 0):
                break
        else:
            print(cx, cy, h)
            exit(0)
exit(1)


### FIXED CODE ###

N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

i = 0
while 1:
    if P[i][2] > 0:
        break
    i += 1
x0, y0, h0 = P[i]
for cy in range(101):
    for cx in range(101):
        h = h0 + abs(cx - x0) + abs(cy - y0)
        for x, y, h1 in P:
            if h1 != max(h - abs(cx - x) - abs(cy - y), 0):
                break
        else:
            print(cx, cy, h)
            exit(0)
exit(1)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
C = list(map(int, input().split()))
C = sorted(C)
AB = [list(map(int, input().split())) for i in range(M)]
AB = sorted(AB, key=lambda x: x[1], reverse=True)
AB = [ab[1] for ab in AB for i in range(ab[0])]

index = min([N, len(AB)])
for i in range(index):
  if AB[i] < C[i]:
    index = i
    break
result = sum(AB[:index])
if index < N:
  result += sum(C[index:])
print(result)

### FIXED CODE ###

def main():
  N, M = list(map(int, input().split()))
  C = list(map(int, input().split()))
  C = sorted(C)
  AB = [list(map(int, input().split())) for i in range(M)]
  AB = sorted(AB, key=lambda x: x[1], reverse=True)
  
  result = 0
  i, j = 0, 0
  while i < N:
    A, B = AB[j] if j < M else (0, 0)
    j += 1
    if i+A < N and B >= C[i+A]:
      i += A
      result += A * B
    else:
      break
    
  while i < N:
    if C[i] > B:
      result += sum(C[i:])
      break
    else:
      result += B
      A -= 1      
      if j < M and A == 0:
        A, B = AB[j] if j < M else (0, 0)
        j += 1
    
    i += 1
  
  print(result)

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

N, M = map(int, input().split())
count = [0]*N
for i in range(M):
    L, R = map(int, input().split())
    for i in range(L, R+1):
        count[i-1] += 1
ans = 0
for i in count:
    if i == M:
        ans += 1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
maxL = 0
minR = float('inf')
for i in range(M):
    L, R = map(int, input().split())
    maxL = max(maxL, L)
    minR = min(minR, R)
if minR - maxL >= 0:
    print(minR - maxL + 1)
else:
    print(0)