github.com/captn3m0/codechef.git

---
{"languages_supported":{"0":"NA"},"title":"C2","category":"NA","old_version":true,"problem_code":"C2","tags":{"0":"NA"},"layout":"problem"}
---

<h3> All submissions for this problem are available. </h3><p>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.</p>

<h3>Input</h3>
<p>First t&lt;=10 - the number of test cases.
Each test case consist of numbers: 1&lt;=n&lt;=1000000000, 1&lt;=k&lt;=100, 1&lt;=p&lt;=1000000000.</p>

<h3>Output</h3>
<p>For each test case, output the value: (1<sup>k</sup>+2<sup>k</sup>+...+n<sup>k</sup>) mod p.</p>

<h3>Example</h3>
<p>For input:
<pre>4
10 1 1000000
10 2 1000000
10 3 1000000
10 4 1000000
</pre>
</p><p>the correct output is:
<pre>55
385
3025
25333
</pre></p>