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

import itertools

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

cumsum = [[0] * (N + 1) for _ in range(N + 1)]
for l, r in LR:
    cumsum[l][r] += 1
for i, j in itertools.product(range(N + 1), range(N)):
    cumsum[i][j + 1] += cumsum[i][j]
for p, q in pq:
    print(sum([cumsum[i][q] - cumsum[i][p - 1] for i in range(p, q + 1)]))

### FIXED CODE ###

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

cumsum = [[0] * (N+2) for _ in range(N+1)]
for lr in LR:
    cumsum[lr[0]][lr[0]] += 1
    if lr[1] < N:
        cumsum[lr[0]][lr[1]+1] -= 1
for i in range(N+1):
    for j in range(i, N):
        cumsum[i][j+1] += cumsum[i][j]
for pq in PQ:
    print(sum([cumsum[i][i]-cumsum[i][pq[1]+1]
               for i in range(pq[0], pq[1]+1)]))
### BUGGY CODE ###

n = int(input())
s = input()
ans = 3*10**5+1
res = 0
for i in range(1,n-1):
    l1 = s[:i-1]
    l2 = s[i+1:]
    res = l1.count("W")+l2.count("E")
    ans = min(ans,res)
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
cnt = s.count("E")
res = cnt
for i in s:
    if i=="E":
        cnt-=1
    else:
        cnt+=1
    res=min(res,cnt)
print(res)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
now = [1]
ans =1
 
for i in range(k):
    if a[now[i]-1] in now:
        break
    now.append(a[now[i]-1])
 
    
t = len(now)-now.index(a[now[i]-1])
f = now.index(a[now[i]-1])


if k >= f + t:
    p = (k-f)%t
    k = f + p
    
for _ in range(k):
    ans = a[ans-1]
print(ans)

### FIXED CODE ###

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

visited = [None]*n
cur = 0
for i in range(k):
    if visited[cur] is None:
        visited[cur] = i
        cur = a[cur]-1
    else:
        break
else:
    print(cur+1)
    sys.exit()

k -= i
k %= i-visited[cur]

for i in range(k):
    cur = a[cur]-1

print(cur+1)
### BUGGY CODE ###

N,K = map(int,input().split())
for i in range(N):
    if N >=2**i and N <2**(i+1):
        print(i+1)

### FIXED CODE ###

N,K = map(int,input().split())
for i in range(N):
    if N >=K**i and N <K**(i+1):
        print(i+1)
        break
### BUGGY CODE ###

N,Q = map(int, input().split())
S = list(input())
lr = [list(map(int,input().split())) for i in range(Q)]
bef = ''
pos = []
for idx,val in enumerate(S):
    if val == 'C' and bef == 'A':
        pos.append((idx -1) * 10 + idx)
    bef = val

cnt = 0
for i in range(Q):
    min_v = (lr[i][0] - 1) * 10 + lr[i][0]
    max_v = (lr[i][1] - 2) * 10 + (lr[i][1] - 1)
    n = sum(1 for x in pos if x >= min_v and x <= max_v)
    print(n)



### FIXED CODE ###

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

total = []
total.append(0)
for i in range(1, N):
    if S[i - 1] == 'A' and S[i] == 'C':
        total.append(1)
    else:
        total.append(0)
totsum = 0
for idx, val in enumerate(total):
    totsum += val
    total[idx] = totsum

for lr in lrs:
    print(total[lr[1] - 1] - total[lr[0] - 1])
### BUGGY CODE ###

n=int(input())
p=list(map(float,input().split()))
dp=[[0 for j in range(n+1)] for i in range(n+1)]

dp[0][0]=1
for i in range(n):
  for j in range(i+1):
    dp[i+1][j+1]+=dp[i][j]*p[i]
    dp[i+1][j]+=dp[i][j]*(1-p[i])
ans=0
for i in range(n,-1,-1):
  if i>n-i:
    ans+=dp[-1][i]
  else:
    break
print(ans)


### FIXED CODE ###

n=int(input())
p=list(map(float,input().split()))
dp=[[0 for j in range(n+1)] for i in range(n+1)]

dp[0][0]=1
for i in range(n):
  for j in range(n):
    dp[i+1][j+1]+=dp[i][j]*p[i]
    dp[i+1][j]+=dp[i][j]*(1-p[i])
ans=0
for i in range(n,-1,-1):
  if i>n-i:
    ans+=dp[-1][i]
  else:
    break
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    if i==0:
        ans = a[0]
    else:
        ans *= a[i]
if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if 0 in a:
    print(0)
else:
    for i in range(n):
        if i==0:
            ans = a[0]
        else:
            ans *= a[i]
            if 1000000000000000000<ans:
                break
    if ans > 1000000000000000000:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

a = sorted(a)
b = sorted(b)
c = sorted(c)

ans = 0

for x in reversed(a):
    for y in reversed(b):
        if x < y:
            for z in reversed(c):
                if y < z:
                    ans += 1
                else:
                    break
        else:
            break

print(ans)

### FIXED CODE ###

import bisect

n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

a = sorted(a)
b = sorted(b)
c = sorted(c)

ans = 0

for x in b:
    aa = bisect.bisect_left(a,x)
    cc = len(c) - bisect.bisect_right(c,x)
    ans += aa * cc

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

K = int(input())
s = len(input())

mod = 10 ** 9 + 7
N = 2 * 10**6
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
  fac.append( ( fac[-1] * i ) % mod )
  inv.append( mod - ( inv[mod % i] * (mod // i) % mod ) )
  finv.append( finv[-1] * inv[-1]  % mod )

def cmb(n, r):
  return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod

p25 = [1]
p26 = [1]

for i in range(K):
  p25.append(p25[i]*25%mod)
  p26.append(p26[i]*26%mod)

ans = 0

for i in range(K+1):
  ans += ( cmb(s+K-i-1, s-1) * p25[K-i] % mod ) * p26[i] % mod

print(ans)

### FIXED CODE ###

K = int(input())
S = input()
s = len(S)
L = []

mod = 10 ** 9 + 7
N = 2 * 10**6
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]

def cmb(n, r):
  return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod
 
for i in range(2, N + 1):
  fac.append( ( fac[-1] * i ) % mod )
  inv.append( mod - ( inv[mod % i] * (mod // i) % mod ) )
  finv.append( finv[-1] * inv[-1]  % mod )

for i in range(K+1):
  L.append( cmb(i+s-1, s-1) * pow(25, i, mod) % mod )

ans = []

for i, x in enumerate(L):
  if i == 0:
    ans.append(x)
  else:
    ans.append( ( ans[i-1]*26%mod + x ) % mod )

print(ans[K])
### BUGGY CODE ###

characteristic=10**9+7
def plus(input1,input2):
    return (input1+input2)%characteristic
def minus(input1,input2):
    return (input1-input2)%characteristic
def times(input1,input2):
    return (input1*input2)%characteristic
'''
def exponen(input1,input2):
    binaryl=list(str(bin(input2))[2:])
    binarysize=len(binaryl)
    binarylist=[int(binaryl[binarysize-1-i]) for i in range(binarysize)]
    modlist=[0 for i in range(binarysize)]
    modlist[0]=input1
    for i in range(1,binarysize):
        modlist[i]=times(modlist[i-1],modlist[i-1])
    answer=1
    for i in range(binarysize):
        if binarylist[i]==1:
            answer=times(answer,modlist[i])
    return answer
'''
def exponen(input1,input2):
    if input2==0:
        return 1
    elif input2%2==0:
        return exponen(times(input1,input1),input2//2)
    else:
        return times(input1,exponen(times(input1,input1),input2//2))

def divide(input1,input2):
    return times(input1,exponen(input2,characteristic-2))
N=int(input())
Fact=[1 for i in range(N+1)]
Finv=[1 for i in range(N+1)]
for i in range(1,N+1):
    Fact[i]=times(Fact[i-1],i)
    Finv[i]=divide(1,Fact[i])
ans=0
SGL=[0 for i in range(N)]
for K in range(N):
    if 2*K-N<0:
        continue
    SGL[K]=times(times(Fact[K],Finv[2*K-N]),Fact[K-1])
for K in range(1,N):
    ans=plus(ans,times(SGL[K]-SGL[K-1],K))
print(ans)


### FIXED CODE ###

P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
N=int(input())
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(N):
    Fact[i+1]=((i+1)*Fact[i])%P
    Finv[i+1]=(Finv[i]*inv(i+1))%P
SGN=[0 for i in range(N)]
ans=0
for k in range(N):
    if 2*k-N>=0:
        SGN[k]=(((Fact[k-1]*Fact[k])%P)*Finv[2*k-N])%P
        ans=(ans+k*(SGN[k]-SGN[k-1]))%P
print(ans)
### BUGGY CODE ###

import itertools

while 1:
    try:
      a, b= map(int, raw_input().split())
      GCD = a * b
      LCM = 0
      # GCD
      for i, j in itertools.product(range((a if a > b else b) / 2), repeat=2):
          if a * (i+1) == b * (j+1) and GCD > a * (i+1):
              GCD = a * (i+1)
      # LCM
      flag = 0
      for i in range(a if a > b else b, 1, -1):
          if a % i == 0 and b % i == 0 and flag == 0:
              LCM = i
              flag += 1
      print "{} {}".format(str(GCD), str(LCM))
    except:
      break

### FIXED CODE ###

def get_gcd(a,b):
	if a > b: a, b = b, a
	if b % a == 0:
		return a
	else:
		return get_gcd(a, b % a)

def get_lcm(a,b,g):
	return a * b / g

while True:
	try:
		a,b = map(int, sorted(raw_input().split()))
		GCD = get_gcd(a,b)
		LCM = get_lcm(a,b,GCD)
		print "{} {}".format(GCD, LCM)
	except EOFError:
		break
### BUGGY CODE ###

R,C,K=map(int,input().split())
l=[[0] * C for i in range(R)]
dp=[[[0] * R for i in range(C)] for j in range(4)]
for i in range(K):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  l[a][b]=c
dp[1][0][0]=l[0][0]
for x in range(1,R+C-1):
  for y in range(R):
    i=y
    j=x-y
    if j<0 or C<=j:
      continue
    for k in range(4):
      A=0
      if 0<j:
        A=max(A,dp[k][j-1][i])
        if 0<k:
          A=max(A,dp[k-1][j-1][i]+l[i][j])
      if 0<i and k<2:
        for q in range(4):
          A=max(A,dp[q][j][i-1]+k*l[i][j])
      dp[k][j][i]=A
X=dp[3][C-1][R-1]
for k in range(3):
  X=max(X,dp[k][C-1][R-1])
print(X)

### FIXED CODE ###

R,C,K=map(int,input().split())
l=[[0] * C for i in range(R)]
for i in range(K):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  l[a][b]=c
dp=[0]*C
for i in range(R):
  ndp=[0]*C
  kdp=[0]*4
  kdp[0]=dp[0]
  kdp[1]=l[i][0]+dp[0]
  ndp[0]=kdp[1]
  for j in range(1,C):
    kdp[0]=max(kdp[0],dp[j])
    for k in range(2,-1,-1):
      kdp[k+1]=max(kdp[k+1],kdp[k]+l[i][j])
    ndp[j]=max(kdp)
  dp=ndp
print(dp[C-1])
### BUGGY CODE ###

import math
import sys
import os
import numpy as np

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

N,K = LI()
P = LI()
C = LI()

P = list(map(lambda x:x-1,P))

res = -INF
used = [False] * N
ss = []

for i in range(N):
    # print('i',i)
    if used[i]:
        continue
    cur = i
    s = []
    while not used[cur]:
        used[cur] = True
        s.append(C[cur])
        cur = P[cur]
        # print(cur)
    ss.append(s)

# print(ss)

for vec in ss:
    M = len(vec)
    # 2周の累積和
    sum = [0]*(2*M + 1)
    for i in range(2*M):
        sum[i+1] = sum[i]+vec[i%M]
    
    # amari[r] := 連続するr個の最大値
    amari = [-INF]*M
    for i in range(M):
        for j in range(M):
            amari[j] = max(amari[j],sum[i+j] - sum[i])
    
    for r in range(M):
        if r>K:
            continue
        q = (K-r)//M
        if r==0 and q==0:
            continue
        if sum[M]>0:
            res = max(res, amari[r] + sum[M] * q)
        elif r > 0:
            res = max(res, amari[r])
print(res)




### FIXED CODE ###

import math
import sys
import os

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

N,K = LI()
P = LI()
C = LI()

P = list(map(lambda x:x-1,P))

res = -INF
used = [False] * N
ss = []

for i in range(N):
    # print('i',i)
    if used[i]:
        continue
    cur = i
    s = []
    while not used[cur]:
        used[cur] = True
        s.append(C[cur])
        cur = P[cur]
        # print(cur)
    ss.append(s)

# print(ss)

for vec in ss:
    M = len(vec)
    # 2周の累積和
    sum = [0]*(2*M + 1)
    for i in range(2*M):
        sum[i+1] = sum[i]+vec[i%M]
    
    # amari[r] := 連続するr個の最大値
    amari = [-INF]*M
    for i in range(M):
        for j in range(M):
            amari[j] = max(amari[j],sum[i+j] - sum[i])
    
    for r in range(M):
        if r>K:
            continue
        q = (K-r)//M
        if r==0 and q==0:
            continue
        if sum[M]>0:
            res = max(res, amari[r] + sum[M] * q)
        elif r > 0:
            res = max(res, amari[r])
print(res)
### BUGGY CODE ###

from functools import reduce
from itertools import combinations
from fractions import gcd
 
def get_gcd(number_list):
    return reduce(gcd, number_list)
 
N = int(input())
Numbers = list(map(int, input().split()))
 
skipped = list(combinations(Numbers, N - 1))
 
gcd_list = [get_gcd(item) for item in skipped]
    
print(int(max(gcd_list)))

### FIXED CODE ###

from functools import reduce
from itertools import combinations
from fractions import gcd

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


Left = [0] * (N + 1)
Right = [0] * (N + 1)

for i in range(N):
    Left[i + 1] = gcd(Left[i], A[i])
    Right[N - i - 1] = gcd(Right[N - i], A[N - i - 1])
ans = 0
for i in range(N):
    ans = max(ans, gcd(Left[i], Right[i + 1]))
    
print(ans)
### BUGGY CODE ###

t, p = input(), input()
start, len_p = 0, len(p)
while True:
    idx = t.find(p, start)
    if idx == -1:
        break
    print(idx)
    start = idx + 1

### FIXED CODE ###

def make_kmp_table(t):
    i = 2
    j = 0
    m = len(t)
    tbl = [0] * (m + 1)
    tbl[0] = -1
    while i <= m:
        if t[i - 1] == t[j]:
            tbl[i] = j + 1
            i += 1
            j += 1
        elif j > 0:
            j = tbl[j]
        else:
            tbl[i] = 0
            i += 1
    return tbl


def kmp(s, t):
    matched_indices = []
    tbl = make_kmp_table(t)
    i = 0
    j = 0
    n = len(s)
    m = len(t)
    while i + j < n:
        if t[j] == s[i + j]:
            j += 1
            if j == m:
                matched_indices.append(i)
                i += j - tbl[j]
                j = tbl[j]
        else:
            i += j - tbl[j]
            if j > 0:
                j = tbl[j]
    return matched_indices


t = input()
p = input()
result = kmp(t, p)
if result:
    print(*result, sep='\n')
### BUGGY CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    
    H, N = map(int, input().split())

    INF = 1001001001
    dp = [INF]*(H+1)

    dp[0] = 0
    for i in range(N):
        a, b = map(int, input().split())
        for j in range(H):
            nj = min(j+a, H)
            dp[nj] = min(dp[nj], dp[j] + b)

    print(dp[H])


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import math

def resolve():
    import sys
    input = sys.stdin.readline
    
    H, N = map(int, input().split())
    v = []
    w = []
    for i in range(N):
        a, b = map(int, input().split())
        v.append(a)
        w.append(b)

    dp = [[0]*H for _ in range(N)]

    # initiate
    for i in range(H):
        dp[0][i] = w[0] * (math.ceil((i + 1) / v[0])) # 魔法1だけでHまで削るのに必要なコスト(MP)

    for i in range(1, N):
        for j in range(H):
            if j+1 < v[i]: 
                # 敵のHPが魔法iで与えるダメージより小さい場合、そのままの組み合わせか新しい魔法1回とで、コストの少ない方を選ぶ
                dp[i][j] = min(dp[i-1][j], w[i])
            else:
                # 大きい場合、そのままの組み合わせと、魔法iを取り込んだ組み合わせで、コストの少ない方を選ぶ
                dp[i][j] = min(dp[i-1][j], dp[i][j - v[i]] + w[i])

    print(dp[N-1][H-1])


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

import copy
def hashnum(state):
    num = 0
    for i in range(3):
        for j in range(3):
            num *= 10
            num += state[i][j]
    return num

answer = 123456780
ini_state = []
for i in range(3):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        zero_x, zero_y = temp.index(0), i
    ini_state.append(temp)
queue = [[ini_state, zero_x, zero_y]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = set()
visited |= {hashnum(ini_state)}
trial = 0
while answer not in visited:
    new_queue = []
    for q in queue:
        state, zero_x, zero_y = q
        for i in range(len(dx)):
            new_state = copy.deepcopy(state)
            new_x = zero_x + dx[i]
            new_y = zero_y + dy[i]
            if 0 <= new_x < 3 and 0 <= new_y < 3:
                new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                perm = hashnum(new_state)
                if perm not in visited:
                    visited |= {perm}
                    new_queue.append([new_state, new_x, new_y])
    queue = new_queue
    trial += 1
print(trial)

### FIXED CODE ###

import copy
def hashnum(state):
    num = 0
    for i in range(3):
        for j in range(3):
            num *= 10
            num += state[i][j]
    return num

answer = 123456780
ini_state = []
for i in range(3):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        zero_x, zero_y = temp.index(0), i
    ini_state.append(temp)
end_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
queue = [[ini_state, zero_x, zero_y, 0], [end_state, 2, 2, 1]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
if hashnum(ini_state) == answer:
    print(0)
else:
    visited[hashnum(ini_state)] = [0, 0]
    visited[answer] = [0, 1]
    trial = 0
    ended = 0
    while queue:
        new_queue = []
        trial += 1
        for q in queue:
            if ended:
                break
            state, zero_x, zero_y, direction = q
            for i in range(len(dx)):
                new_state = copy.deepcopy(state)
                new_x = zero_x + dx[i]
                new_y = zero_y + dy[i]
                if 0 <= new_x < 3 and 0 <= new_y < 3:
                    new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                    perm = hashnum(new_state)
                    if perm in visited and direction != visited[perm][1]:
                        print(trial + visited[perm][0])
                        ended = 1
                        break
                    elif perm not in visited:
                        visited[perm] = [trial, direction]
                        new_queue.append([new_state, new_x, new_y, direction])
        queue = new_queue
### BUGGY CODE ###

n = int(input())
ns = [int(input()) for _ in range(n)]
i = 0
cnt = 0
pushed = [0]
flg = False
while(True):
    cnt += 1
    i = ns[i] - 1
    if i in pushed:
        break
    pushed.append(i)
    if i == 1:
        flg = True
        break
if flg:
    print(cnt)
else:
    print(-1)

### FIXED CODE ###

import sys
n = int(input())
ns = [int(input()) for _ in range(n)]
if not 2 in ns:
    print(-1)
    sys.exit(0)
i = 0
cnt = 0
pushed = [0]*n
flg = False
while(True):
    cnt += 1
    i = ns[i] - 1
    if pushed[i] == 1:
        break
    pushed[i] = 1
    if i == 1:
        flg = True
        break
if flg:
    print(cnt)
else:
    print(-1)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush

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

lst = [list(map(int, input().split())) for s in range(N)]
lst = sorted(lst, key=lambda x: (x[0], -x[1]))

heap = []
heapify(heap)
r = 0
for i in range(1, M + 1):
    # i日後
    while lst and lst[0][0] <= i:
        v = lst.pop(0)[1]
        heappush(heap, -v)

    if len(heap) != 0:
        r += heappop(heap) * (-1)

print(r)

### FIXED CODE ###

from heapq import heapify, heappop, heappush
from collections import defaultdict

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

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

dic = defaultdict(list)
for a, b in lst:
    dic[a].append(b)

heap = []
heapify(heap)

r = 0
for i in range(1, M + 1):
    can = dic[i]
    while can:
        heappush(heap, -can.pop(0))

    if len(heap) != 0:
        r += heappop(heap) * (-1)

print(r)
### 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(max(m,n))**2//max(m,n)%mod)
else:
    print(factorial(n)**2*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 ###

from math import ceil
N = int(input())
A = [int(a) for a in input().split()]

DP = [[False for i in range(max(A) * N + 1)] for n in range(N)]
DP[0][0], DP[0][A[0]] = True, True
maxN = A[0]
for i in range(1, N):
    a = A[i]
    for j in range(maxN+1):
        if DP[i-1][j]:
            DP[i][j] = True
            DP[i][j + a] = True
    maxN += a

for i in range(ceil(sum(A)/2), max(A) * N + 1):
    if DP[N-1][i]:
        print(i)
        break


### FIXED CODE ###

from math import ceil
N = int(input())
A = [int(a) for a in input().split()]

DP = 1
for a in A:
    DP |= DP << a

Shalf = ceil(sum(A)/2)
DP >>= Shalf
for i in range(N * max(A)):
    if DP & 1:
        print(Shalf + i)
        break
    DP >>= 1
### BUGGY CODE ###

n,k = map(int,input().split())
x = []
y = []
for i in range(n):
	a,b = map(int,input().split())
	x.append(a)
	y.append(b)
ans = 10 ** 100
for j in range(n):
	for f in range(n):
		for h in range(n):
			for g in range(n):
				cou = 0
				for t in range(n):
					if x[j] <= x[t] <= x[f] and y[h] <= y[t] <= y[g]:
						cou += 1
				if cou >= k:
					ans = min(ans,abs(x[j] - x[f]) * abs(y[h] - y[g]))
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
x = []
y = []
xx = []
yy = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    xx.append(a)
    yy.append(b)
ans = 10 ** 40
x.sort()
y.sort()
for i in range(n):
    for j in range(i+1,n):
        for l in range(n):
            for h in range(l+1,n):
                lx = x[i]
                rx = x[j]
                uy = y[h]
                dy = y[l]
                cnt = 0
                for ii in range(n):
                    if lx <= xx[ii] <= rx and dy <= yy[ii] <= uy:
                        cnt += 1
                if cnt >= k:
                    if (rx-lx) * (uy-dy) != 0:
                        ans = min(ans,(rx-lx)*(uy-dy))
print(ans)
### BUGGY CODE ###


if __name__ == "__main__":
    n,k = map(int,input().split())
    arr = list(map(int,input().split()))
    dp = [-1]*len(arr)
    curr = 1 
    dp[0] = 0
    dp[1] = abs(arr[1]-arr[0])
    cost = 0
    for i in range(2,len(arr)):
        m = float("inf")
        x = i-1
        c = 0
        while(x>=0 and c<k):
            m= min(m,dp[x]+abs(arr[i]-arr[x]))
            x -= 1
            c += 1 
        dp[i] = m
    print(dp[-1]) 

### FIXED CODE ###


n,k = map(int,input().split())
arr = list(map(int,input().split()))
dp = [float("inf")]*len(arr)
dp[0] = 0
cost = 0
for i in range(len(arr)):
    for jump in range(i+1,i+k+1):
        if(jump<len(arr)):
            dp[jump] = min(dp[jump],dp[i]+abs(arr[jump]-arr[i]))
print(dp[-1])
### BUGGY CODE ###

A, B, N = map(int, raw_input().split())
def f(x):
    return int(A*x/float(B)) - A * int(x/float(B))

score = 0
max_score = 0

for x in xrange(N+1):
    score = f(x)
    if score >= max_score:
        max_score = score
    else:
        break

print max_score


### FIXED CODE ###

A, B, N = map(int, raw_input().split())
def f(x):
    return int(A*x/float(B)) - A * int(x/float(B))

print f(min(N, B - 1))