Let us calculate the sum of k-th powers of natural numbers from 1 to n. As the result can be quite large, output the result modulo some integer p.

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

First t≤10 - the number of test cases.
Each test case consist of numbers: 1≤n≤1000000000, 1≤k≤100, 1≤p≤1000000000.

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

For each test case, output the value: (1^{k}+2^{k}+...+n^{k}) mod p.

----- Sample Input 1 ------ 
4
10 1 1000000
10 2 1000000
10 3 1000000
10 4 1000000
----- Sample Output 1 ------ 
55
385
3025
25333

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Number theory

Combinatorics

Mathematics


Solutions:
t = int(input())
for i in range(t):
	(a, b, o) = map(int, input().split())
	r = 10 ** 2 + 5
	(d, s) = ([0] * 10 ** 5, [0] * r)
	for j in range(r):
		for k in range(r):
			if j == k or k == 0:
				d[j * r + k] = 1
			else:
				d[j * r + k] = d[(j - 1) * r + k - 1] + d[(j - 1) * r + k]
	for j in range(b + 1):
		ans = pow(a + 1, j + 1) - 1
		for k in range(j):
			ans -= d[(j + 1) * r + k] * s[k]
		s[j] = ans // (j + 1)
	print(s[b] % o)


ln = 10 ** 2 + 5
for _ in range(int(input())):
	(n, k, p) = list(map(int, input().split()))
	(d, s) = ([0] * 10 ** 5, [0] * ln)
	for i in range(ln):
		for j in range(ln):
			d[i * ln + j] = 1 if i == j or j == 0 else d[(i - 1) * ln + j - 1] + d[(i - 1) * ln + j]
	for i in range(k + 1):
		ans = pow(n + 1, i + 1) - 1
		for j in range(i):
			ans -= d[(i + 1) * ln + j] * s[j]
		s[i] = ans // (i + 1)
	print(s[k] % p)


for _ in range(int(input())):
	(a, b, out) = map(int, input().split())
	r = 10 ** 2 + 5
	(d, s) = ([0] * 10 ** 5, [0] * r)
	for i in range(r):
		for j in range(r):
			d[i * r + j] = 1 if i == j or j == 0 else d[(i - 1) * r + j - 1] + d[(i - 1) * r + j]
	for i in range(b + 1):
		ans = pow(a + 1, i + 1) - 1
		for j in range(i):
			ans -= d[(i + 1) * r + j] * s[j]
		s[i] = ans // (i + 1)
	print(s[b] % out)