Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef is experimenting in his kitchen. He has $N$ spices (numbered $0$ through $N-1$) with types $S_{0}, S_{1}, \ldots, S_{N-1}$.

You should answer $Q$ queries. Each query is described by two integers $L$ and $R$. In each query, Chef wants to use the spices $S_{L}, S_{L+1}, \ldots, S_{R}$ in some order to make a dish. However, he has no clue about the order in which he should use them to make a perfect dish, so he wants to try all possible orders (sequences created by permuting these $R-L+1$ spices) to find out. Tell Chef the number of distinct orders (sequences) of spices he needs to try. Since this number can be very large, compute it modulo $10^{9}+7$.

Two sequences of spices are considered different if there is a valid index $i$ such that the type of the $i$-th spice in one sequence is different from the type of the $i$-th spice used in the other sequence.

Note that the input is encoded so that you have to answer the queries online.
  
------  Input ------
The first line of the input contains two space-separated integers $N$ and $Q$.
The next line contains $N$ space-separated integers $S_{0}, S_{1}, S_{2}, \ldots, S_{N-1}$.
Each of the next $Q$ lines contains four space-separated integers $L_{1}$, $L_{2}$, $R_{1}$ and $R_{2}$ describing a query. The parameters $L$ and $R$ can be calculated in the following way:
- Let's denote the answer to the previous query by $a$; for the first query, $a = 0$.
- Calculate $L = (L_{1} \cdot a + L_{2}) \% N$ and $R = (R_{1} \cdot a + R_{2}) \% N$.
- Then, if $L > R$, swap $L$ and $R$.

------  Output ------
For each query, print a single line containing one integer — the number of distinct orders of spices modulo $10^{9}+7$.

------  Constraints ------
$1 ≤ N, Q ≤ 3 \cdot 10^{5}$
$1 ≤ S_{i} ≤ 10^{9}$ for each valid $i$
$0 ≤ L_{1}, L_{2}, R_{1}, R_{2} ≤ N-1$

------  Subtasks ------
Subtask #1 (10 points): $1 ≤ N, Q ≤ 10^{3}$

Subtask #2 (40 points):
$1 ≤ N, Q ≤ 10^{5}$
$L_{1} = R_{1} = 0$

Subtask #3 (30 points): $1 ≤ N, Q ≤ 10^{5}$

Subtask #4 (20 points): original constraints

----- Sample Input 1 ------ 
5 3

1 2 3 7 10

1 1 1 1

2 1 3 4

0 0 0 4
----- Sample Output 1 ------ 
1

2

120

Source: codechef | Difficulty: VERY_HARD
Tags: Square root algorithms

Combinatorics

Sweep line algorithms

Preprocessing

Mathematics


Solutions:
def exponent(a, y, m):
	if y == 0:
		return 1
	ss = y // 2
	an = exponent(a, ss, m)
	an = an * an % m
	if y % 2 == 0:
		return an
	else:
		return a * an % m
import bisect
(n, q) = map(int, input().split())
it = list(map(int, input().split()))
a = [1]
x = 10 ** 9 + 7
for i in range(1, n + 1):
	a.append(a[-1] * (i + 1) % x)
ind = {}
freq = {}
mult = [[] for i in range(n)]
ii = 0
for (j, i) in enumerate(it):
	try:
		freq[i].append(j)
		if len(freq[i]) == 2:
			ind[i] = ii
			ii += 1
			mult[ind[i]].append(freq[i][0])
		try:
			mult[ind[i]].append(j)
		except:
			pass
	except:
		freq[i] = [j]
ans = 0
dp = {}
for _ in range(q):
	(l1, l2, r1, r2) = map(int, input().split())
	l = (l1 * ans + l2) % n
	r = (r1 * ans + r2) % n
	(l, r) = sorted([l, r])
	ans = a[r - l]
	for ii in ind:
		ii = mult[ind[ii]]
		if ii[0] > r:
			break
		if ii[-1] < l:
			continue
		ij = bisect.bisect_left(ii, l)
		ji = bisect.bisect_right(ii, r)
		if ji > ij + 1:
			try:
				ans = ans * dp[ji - ij - 1]
			except:
				dp[ji - ij - 1] = exponent(a[ji - ij - 1], x - 2, x)
				ans = ans * dp[ji - ij - 1]
			ans = ans % x
	print(ans % x)


import copy

def hins(s1, n1, prime):
	if n1 == 1:
		return s1 % prime
	elif n1 == 0:
		return 1
	elif n1 % 2 == 0:
		z = hins(s1, n1 // 2, prime)
		z = z * z % prime
		return z
	else:
		z = hins(s1, n1 // 2, prime)
		z = z * z % prime
		return s1 % prime * z % prime
(n, q) = map(int, input().split())
p = list(map(int, input().split()))
p1 = copy.deepcopy(p)
p1.sort()
repeat = {}
ans = 0
prime = 1000000007
d = {}
s1 = []
s1.append(1)
s2 = []
first_count = {}
for i in range(1, n + 1):
	k = s1[i - 1] * i
	k = k % prime
	s1.append(k)
	repeat[p[i - 1]] = 0
for i in range(0, len(p1) - 1):
	if p1[i] == p1[i + 1]:
		repeat[p1[i]] = 1
	elif repeat[p1[i]] != 1:
		repeat[p1[i]] = 0
for i in range(0, n):
	d[p[i]] = 0
	s2.append({})
for i in range(n - 1, -1, -1):
	d[p[i]] = d[p[i]] + 1
	if repeat[p[i]] == 1 and i != n - 1:
		f = {}
		f = copy.deepcopy(s2[i + 1])
		f[p[i]] = d[p[i]]
		s2[i] = f
	elif repeat[p[i]] == 0 and i != n - 1:
		s2[i] = copy.deepcopy(s2[i + 1])
	elif repeat[p[i]] == 1 and i == n - 1:
		f = {}
		f[p[i]] = d[p[i]]
		s2[i] = f
for i in range(0, q):
	a = 0
	a = ans
	(l1, l2, r1, r2) = map(int, input().split())
	l = (l1 * a + l2) % n
	r = (r1 * a + r2) % n
	if l > r:
		y = l
		l = r
		r = y
	k = s1[r - l + 1]
	ans = k
	ans = ans % prime
	ans2 = 1
	mai = {}
	if r < n - 1:
		p1 = s2[l]
		p2 = s2[r + 1]
		for j in p1:
			try:
				x = p1[j] - p2[j]
				ans2 = ans2 % prime * (s1[x] % prime)
				ans2 = ans2 % prime
			except:
				ans2 = ans2 % prime * (s1[p1[j]] % prime)
				ans2 = ans2 % prime
	else:
		p1 = s2[l]
		for j in p1.keys():
			ans2 = ans2 % prime * (s1[p1[j]] % prime)
			ans2 = ans2 % prime
	ans2 = hins(ans2, prime - 2, prime)
	ans2 = ans2 % prime
	ans = ans * ans2 % prime
	print(ans)


import sys

def exponent(a, y, m):
	return pow(a, y, m)
import bisect
(n, q) = map(int, input().split())
it = list(map(int, input().split()))
a = [1]
x = 10 ** 9 + 7
for i in range(1, n + 1):
	a.append(a[-1] * (i + 1) % x)
ind = {}
freq = {}
mult = [[] for i in range(n)]
ii = 0
for (j, i) in enumerate(it):
	try:
		freq[i].append(j)
		if len(freq[i]) == 2:
			ind[i] = ii
			ii += 1
			mult[ind[i]].append(freq[i][0])
		try:
			mult[ind[i]].append(j)
		except:
			pass
	except:
		freq[i] = [j]
ans = 0
dp = {}
for _ in range(q):
	(l1, l2, r1, r2) = map(int, sys.stdin.readline().split())
	l = (l1 * ans + l2) % n
	r = (r1 * ans + r2) % n
	(l, r) = sorted([l, r])
	ans = a[r - l]
	for ii in ind:
		ii = mult[ind[ii]]
		if ii[0] > r:
			break
		if ii[-1] < l:
			continue
		ij = bisect.bisect_left(ii, l)
		ji = bisect.bisect_right(ii, r)
		if ji > ij + 1:
			try:
				ans = ans * dp[ji - ij - 1]
			except:
				dp[ji - ij - 1] = exponent(a[ji - ij - 1], x - 2, x)
				ans = ans * dp[ji - ij - 1]
			ans = ans % x
	sys.stdout.write(str(ans % x) + '\n')


from copy import deepcopy as dc

def fpower(b, p, n):
	if p == 0:
		return 1
	if p == 1:
		return b % n
	x = fpower(b, p // 2, n)
	ans = x * x % n
	if p % 2 == 0:
		return ans
	else:
		return b % n * ans % n
(n, q) = map(int, input().split())
s = list(map(int, input().split()))
mods = 1000000007
a = 0
sSort = s[:]
sSort.sort()
repeatingNums = {}
for i in range(len(sSort)):
	if i != n - 1:
		if sSort[i] == sSort[i + 1]:
			repeatingNums[sSort[i]] = 1
suffixArr = [-1] * n
suffixArr[n - 1] = {}
for i in range(n - 1, -1, -1):
	try:
		if repeatingNums[s[i]] == 1:
			if i == n - 1:
				d = {}
				d[s[i]] = 1
				suffixArr[i] = d
			else:
				try:
					d = dc(suffixArr[i + 1])
					if type(d[s[i]]) == int:
						d[s[i]] += 1
						suffixArr[i] = d
				except KeyError:
					d = dc(suffixArr[i + 1])
					d[s[i]] = 1
					suffixArr[i] = d
	except:
		if i != n - 1:
			suffixArr[i] = dc(suffixArr[i + 1])
fact = []
fact.append(1)
for i in range(1, n + 1):
	fact.append(fact[-1] * i % mods)
for i in range(q):
	(l1, l2, r1, r2) = map(int, input().split())
	l = (l1 * a + l2) % n
	r = (r1 * a + r2) % n
	if l > r:
		x = l
		l = r
		r = x
	denom = 1
	if r == n - 1:
		ok = suffixArr[l]
		for i in ok:
			denom = denom % mods * (fact[ok[i]] % mods) % mods
	else:
		ok1 = suffixArr[l]
		ok2 = suffixArr[r + 1]
		for i in ok1:
			try:
				xx = ok1[i] - ok2[i]
			except KeyError:
				xx = ok1[i]
			denom = denom % mods * (fact[xx] % mods) % mods
	t = fpower(denom, mods - 2, mods)
	ans = fact[r - l + 1] % mods * t % mods
	a = ans
	print(ans)


def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
arrtemp = arr[:]
arrtemp.sort()
dicti = {}
for i in range(1, n):
	if arrtemp[i - 1] == arrtemp[i]:
		dicti[arrtemp[i]] = True
count = [{} for i in range(n)]
if dicti.get(arr[0], False):
	count[0][arr[0]] = 1
for i in range(1, n):
	for j in count[i - 1]:
		count[i][j] = count[i - 1][j]
	if dicti.get(arr[i], False):
		count[i][arr[i]] = count[i].get(arr[i], 0) + 1
facti = [1, 1]
fact = 1
m = 1000000007
for i in range(2, n + 1):
	fact = fact * i % m
	facti.append(fact)
ans = 0
for i in range(q):
	(l1, l2, r1, r2) = map(int, input().split(' '))
	L = (l1 * ans + l2) % n
	R = (r1 * ans + r2) % n
	if L > R:
		(L, R) = (R, L)
	possmul = 1
	ans = facti[R - L + 1]
	if L == 0:
		for j in list(count[R].values()):
			possmul = possmul * facti[j] % m
	else:
		for j in list(count[R].keys()):
			possmul = possmul * facti[count[R][j] - count[L - 1].get(j, 0)] % m
	if possmul != 1:
		possmul = modInverse(possmul, m)
	ans = ans * possmul % m
	print(ans)


mod = 10 ** 9 + 7
f = [1]
for i in range(1, 10 ** 6):
	f.append(f[i - 1] * i % mod)

def modinv(a, m):
	g = gcd(a, m)
	if g != 1:
		return 0
	else:
		return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p ** 2 % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

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

def minus(d1, d2):
	s = 1
	for i in d1.keys():
		if i in d2:
			s = s * f[d1[i] - d2[i]] % mod
		else:
			s = s * f[d1[i]] % mod
	return s % mod
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
dm = {}
for i in arr:
	if i in dm:
		dm[i] += 1
	else:
		dm[i] = 1
d = {}
pp = []
for i in arr:
	if dm[i] > 1:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	d2 = d.copy()
	pp.append(d2)
a = 0
if len(pp) == 0:
	for _ in range(q):
		(l1, l2, r1, r2) = map(int, input().split())
		l = (l1 * a + l2) % n
		r = (r1 * a + r2) % n
		if l > r:
			(l, r) = (r, l)
		a = f[r - l + 1]
		print(a)
else:
	for _ in range(q):
		(l1, l2, r1, r2) = map(int, input().split())
		l = (l1 * a + l2) % n
		r = (r1 * a + r2) % n
		if l > r:
			(l, r) = (r, l)
		if l == r:
			a = 1
		else:
			if l == 0:
				ans = minus(pp[r], {})
			else:
				ans = minus(pp[r], pp[l - 1])
			a = f[r - l + 1] * (modinv(ans, mod) % mod) % mod
		print(a)


from copy import copy

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
(n, q) = map(int, input().split())
ls = list(map(int, input().split()))
num = 10 ** 9 + 7
fact_list = [1]
a = 1
for i in range(1, n + 1):
	a = a * i % num
	fact_list.append(a)
main_diction = {}
for i in ls:
	try:
		main_diction[i] += 1
	except:
		main_diction[i] = 1
an_main_diction = {}
for i in main_diction.keys():
	if main_diction[i] > 1:
		an_main_diction[i] = main_diction[i]
main_diction = copy(an_main_diction)
base_diction = {}
for i in main_diction.keys():
	base_diction[i] = 0
left_ls = [copy(base_diction)]
next_diction = copy(base_diction)
for i in range(1, n):
	added_element = ls[i - 1]
	try:
		next_diction[added_element] += 1
	except:
		pass
	left_ls.append(copy(next_diction))
base_diction = copy(main_diction)
del_element = ls[0]
try:
	base_diction[del_element] -= 1
except:
	pass
right_ls = [copy(base_diction)]
next_diction = copy(base_diction)
for i in range(1, n):
	del_element = ls[i]
	try:
		next_diction[del_element] -= 1
	except:
		c = 0
	right_ls.append(copy(next_diction))
prev_answer = 0
for i in range(q):
	(l1, l2, r1, r2) = map(int, input().split(' '))
	left_and_right = [(l1 * prev_answer + l2) % n, (r1 * prev_answer + r2) % n]
	left = min(left_and_right)
	right = max(left_and_right)
	cons_left_diction = copy(left_ls[left])
	cons_right_diction = copy(right_ls[right])
	cons_diction = {}
	for j in main_diction.keys():
		if main_diction[j] - cons_left_diction[j] - cons_right_diction[j] > 1:
			cons_diction[j] = main_diction[j] - cons_left_diction[j] - cons_right_diction[j]
	main_cons_diction = {}
	for j in cons_diction.values():
		try:
			main_cons_diction[j] += 1
		except:
			main_cons_diction[j] = 1
	main_list = []
	for j in main_cons_diction.keys():
		main_list.append([j, main_cons_diction[j]])
	first_member = fact_list[right - left + 1]
	second_member = 1
	for j in main_list:
		second_member = second_member * power(fact_list[j[0]], j[1], num) % num
	second_member = power(second_member, num - 2, num)
	answer = first_member * second_member % num
	prev_answer = answer
	print(answer)