Read problems statements in Mandarin Chinese  and Russian. 

For positive integer x let define function F(x) = 1 * (1! + x) + 2 * (2! + x) + .. + x * (x! + x). 
"k!" means factorial: k! = 1 * 2 * .. * k 

Chef wants to calculate F(p_{1}) + F(p_{2}) + ... + F(p_{n}). 
As answer could be large, help him, calculate value modulo m. 

------ Input ------ 

First line contains two integers n and m.
Next line contains n space separated integers p_{i}.

------ Output ------ 

Output a single line containing one integer --- calculated value modulo m.

------ Constraints ------ 

$1 ≤ n_{} ≤  10^{5}$
$1 ≤ p_{i} ≤  10^{18}$
$1 ≤ m ≤  10^{7}$

------  Subtasks  ------ 

$Subtask #1: 1 ≤ p_{i} ≤  6  (10 points)$
$Subtask #2: 1 ≤ p_{i} ≤  7 * 10^{3} (25 points)$
$Subtask #3: m_{}^{} - prime number (25 points)$
$Subtask #4: _{}^{}original constraints (40 points)$

----- Sample Input 1 ------ 
5 7
1 2 3 4 5
----- Sample Output 1 ------ 
6
----- explanation 1 ------ 
F(1) = 1 * (1! + 1) = 2
F(2) = 1 * (1! + 2) + 2 * (2! + 2) = 3 + 8 = 11
F(3) = 1 * (1! + 3) + 2 * (2! + 3) + 3 * (3! + 3) = 4 + 10 + 27 = 41
F(4) = 1 * (1! + 4) + 2 * (2! + 4) + 3 * (3! + 4) + 4 * (4! + 4) = 5 + 12 + 30 + 112 = 159
F(5) = 1 * (1! + 5) + 2 * (2! + 5) + 3 * (3! + 5) + 4 * (4! + 5) + 5 * (5! + 5) = 794
F(1) + F(2) + F(3) + F(4) + F(5) = 2 + 11 + 41 + 159 + 794 = 1007 

1007 modulo 7 = 6

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
import math

def Cout(my_list):
	freq = {}
	for item in my_list:
		if item in freq:
			freq[item] += 1
		else:
			freq[item] = 1
	return freq

def sr(n, m):
	(s, p) = (0, 1)
	if n >= m:
		n = m - 1
	for i in range(1, n + 1):
		p *= i
		p %= m
		s += i * p % m
		s %= m
	return s % m

def ss(n, m):
	m *= 2
	p = n ** 2 % m
	p *= (n + 1) % m
	return p // 2
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
(b, t, s, p, cf) = (Cout(a), 0, 0, 1, [])
for i in range(1, m):
	p *= i + 1
	p = p % m
	s = p - 1 + m
	cf.append(s % m)
for i in b:
	if i >= m:
		r = len(cf) - 1
	else:
		r = i - 1
	y = ss(i, m) + cf[r]
	t += y * b[i]
	t %= m
print(t % m)


def extended_euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	else:
		(d1, x1, y1) = extended_euclid(b, a % b)
		(d, x, y) = (d1, y1, x1 - a // b * y1)
		return (d, x, y)

def modInv(a, n):
	(d, x, y) = extended_euclid(a, n)
	if d == 1:
		return x % n

def recurseFact(n, m):
	if n in cache:
		return cache[n]
	elif n <= 1:
		return 1
	else:
		ans = n * recurseFact(n - 1, m) % m
		cache[n] = ans
		return ans

def fact(n, modulus):
	if n >= modulus:
		ans = 0
	elif n <= modulus // 2:
		ans = recurseFact(n, modulus)
	else:
		ans = recurseFact(modulus - n - 1, modulus)
		ans = modInv(ans, modulus)
		if n % 2 == 0:
			ans = -1 * ans + modulus
	return ans % modulus

def f(n, m):
	M = m * 2
	val1 = (n ** 2 + n ** 3) % M
	val1 //= 2
	val2 = fact(n + 1, m) - 1
	return (val1 + val2) % m
(noOfElements, modulo) = map(int, input().strip().split())
ar = list(map(int, input().strip().split()))
ans = 0
cache = {}
ar.sort()
for p in ar:
	ans += f(p, modulo)
print(ans % modulo)


(n, m) = input().split()
n = int(n)
m = int(m)
a = []
s = 0
a = input().split()
for i in range(len(a)):
	a[i] = int(a[i])
a.sort()
f = a[len(a) - 1]
i = len(a) - 1
while i > 0:
	if a[i] > m:
		f = a[i - 1]
	else:
		break
	i = i - 1
if a[0] >= m:
	f = 0
j = max(a)
g = []
g.append(1)
g.append(1)
if j + 2 < m:
	d = j + 2
else:
	d = f + 2
r = 0
for i in range(2, d):
	if g[i - 1] * i % m != 0:
		g.append(g[i - 1] * i % m)
	else:
		break
for i in range(len(a)):
	p = a[i]
	if p + 1 < len(g):
		s = s + (g[p + 1] + p * p * (p + 1) // 2 % m - 1)
	else:
		s = s + (p * p * (p + 1) // 2 % m - 1)
print(s % m)


def h():
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	S = 0
	start = 2
	cache = 1
	var = 1

	def i_fac_i(x):
		nonlocal cache
		nonlocal var
		s = cache
		for i in range(start, x + 1):
			var = var * (i * i) // (i - 1)
			s = (s + var) % m
		cache = s
		return s
	for p in A:
		if p >= m - 1:
			S = (S + m - 1) % m
		else:
			S = (S + i_fac_i(p)) % m
		start = p + 1
		S = (S + p * p * (p + 1) // 2 % m) % m
	print(S)
h()


def modfac(i, n, m):
	fac = facs[i] * (ints[i] + 1) % m
	nsum = n * n * (n + 1) // 2 % m
	return (fac + nsum - 1) % m

def prod(a, b, m):
	product = 1
	if a // m != b // m:
		return 0
	for i in range(a, b + 1):
		product = product * i % m
		if product == 0:
			return 0
	return product
(n, m) = [int(x) for x in input().strip().split()]
ints = [int(x) for x in input().strip().split()]
ints.sort()
facs = [None] * len(ints)
facs[0] = prod(1, ints[0], m)
for i in range(1, len(ints)):
	facs[i] = facs[i - 1] * prod(ints[i - 1] + 1, ints[i], m) % m
	if not facs[i]:
		for j in range(i + 1, len(ints)):
			facs[j] = 0
		break
sum = 0
for p in range(len(ints)):
	sum = (sum + modfac(p, ints[p], m)) % m
print(sum)


def fastPower(base, n, m):
	if n == 0:
		return 1
	if n == 1:
		return base
	halfn = fastPower(base, n // 2, m)
	if n % 2 == 0:
		return halfn * halfn % m
	else:
		return halfn * halfn % m * base % m

def modInv(n, m):
	return fastPower(n, m - 2, m)

def recurseFact(n, m):
	if n in cache:
		return cache[n]
	elif n < 2:
		return 1
	else:
		ans = n * recurseFact(n - 1, m) % m
		cache[n] = ans
		return ans

def fact(n, modulus):
	if n >= modulus:
		ans = 0
	elif n <= modulus // 2:
		ans = recurseFact(n, modulus)
	else:
		ans = recurseFact(modulus - n - 1, modulus)
		ans = modInv(ans, modulus)
		if n % 2 == 0:
			ans = -1 * ans + modulus
	return ans % modulus

def f(n, m):
	val1 = (n ** 2 + n ** 3) // 2 % m
	val2 = fact(n + 1, m) - 1
	return (val1 + val2) % m
(noOfElements, modulo) = map(int, input().strip().split())
ar = list(map(int, input().strip().split()))
ans = 0
cache = {}
ar.sort()
for p in ar:
	ans += f(p, modulo)
print(ans % modulo)


import math
z = input().split()
(n, m) = map(int, z[:2])
z = input().split()
ps = list(map(int, z[:n]))
facmem = {1: 1}
rf = 1
for afac in range(2, 10000):
	rf = rf * afac % m
	facmem[afac] = rf

def mfac(a):
	if a not in facmem:
		facmem[a] = math.factorial(a)
	return facmem[a]
fcpart = polypart = 0
dm = 2 * m
for p in ps:
	if p < m - 1:
		fcpart += mfac(p + 1) % m
	fcpart -= 1
	p %= dm
	polypart = (polypart + p * p * (p + 1)) % dm
ans = (fcpart + polypart // 2) % m
if ans < 0:
	ans += m
print(ans)


def cal(x, m):
	if x < m:
		return (factorials[x + 1] - 1 + x * x * (x + 1) // 2) % m
	return (x * x * (x + 1) // 2 - 1) % m

def solve(arr, n, m):
	return sum([cal(x, m) for x in arr]) % m
(n, m) = map(int, input().split())
factorials = [1 for i in range(10 ** 7 + 1)]
for i in range(2, 100001):
	factorials[i] = i * factorials[i - 1] % m
arr = list(map(int, input().split()))
print(solve(arr, n, m))


facto = [0] * 1000000

def getfacto(x):
	if x < 1000000:
		return facto[x]
	if x >= m:
		return 0
	ans = x
	return x * getfacto(x - 1) % m
stri = input().split()
n = int(stri[0])
m = int(stri[1])
facto[0] = facto[1] = 1
for i in range(2, 1000000):
	facto[i] = facto[i - 1] * i % m
ans = 0
stri = input().split()
for i in range(n):
	t = int(stri[i])
	ans = (ans + getfacto(t + 1) + t * t * (t + 1) // 2 % m - 1) % m
print(ans)


(n, m) = [int(i) for i in input().split(' ')]
p = [int(i) for i in input().split(' ')]
(fact, F, summ, maxp) = (1, [1], 0, max(p))
for c in range(2, min(m, max(p) + 2)):
	fact = fact * c % m
	F.append(fact)
for i in p:
	if i < m - 1:
		summ += (F[i] + i * i * (i + 1) // 2 - 1) % m
	else:
		summ += (i * i * (i + 1) // 2 - 1) % m
print(summ % m)


from math import *

def f1(x):
	ans = 0
	for k in range(1, x + 1):
		ans += k * (factorial(k) + x)
	return ans

def f2(x):
	return factorial(x + 1) - 1 + x * x * (x + 1) // 2

def test():
	for x in range(1, 21):
		print(x, f1(x), f2(x))

def main():
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	facts = [1, 1]
	for i in range(2, 10 ** 7 + 10):
		facts.append(facts[-1] * i % m)
		if facts[-1] == 0:
			break
	ans = 0
	for n in a:
		if n + 1 <= len(facts) - 1:
			ans = ans + facts[n + 1]
		ans += m - 1
		tmp = n * n * (n + 1) // 2
		ans += tmp
		ans %= m
	print(ans)
main()


(n, m) = map(int, input().split())
F = [1]
for i in range(1, 10000005):
	F.append(i * F[i - 1] % m)
L = list(map(int, input().split()))
ans = 0
for item in L:
	tmp = item * (item + 1) // 2
	tmp %= m
	tmp *= item
	tmp %= m
	if item < m:
		tmp += (F[item + 1] + m - 1) % m
	else:
		tmp += m - 1
	tmp %= m
	ans += tmp
	ans %= m
print(ans)


def fast_Power(base, n, m):
	if n == 0:
		return 1
	if n == 1:
		return base
	halfn = fast_Power(base, n // 2, m)
	if n % 2 == 0:
		return halfn * halfn % m
	else:
		return halfn * halfn % m * base % m

def mod_Inverse(n, m):
	return fast_Power(n, m - 2, m)

def recurse_Fact(n, m):
	if n in cache:
		return cache[n]
	elif n < 2:
		return 1
	else:
		ans = n * recurse_Fact(n - 1, m) % m
		cache[n] = ans
		return ans

def fact(n, modulus):
	if n >= modulus:
		ans = 0
	elif n <= modulus // 2:
		ans = recurse_Fact(n, modulus)
	else:
		ans = recurse_Fact(modulus - n - 1, modulus)
		ans = mod_Inverse(ans, modulus)
		if n % 2 == 0:
			ans = -1 * ans + modulus
	return ans % modulus

def f(n, m):
	val1 = (n * n + n * n * n) // 2 % m
	val2 = fact(n + 1, m) - 1
	return (val1 + val2) % m
(noOfElements, modulo) = map(int, input().strip().split())
ar = list(map(int, input().strip().split()))
ans = 0
cache = {}
ar.sort()
for p in ar:
	ans += f(p, modulo)
print(ans % modulo)