JOIN

 Problem Statement

Problem Statement for Powerit

### Problem Statement

You are given three ints: n, k, and m.

For each i between 1 and n, inclusive, Fox Ciel calculated the number i^(2^k - 1). ("^" denotes exponentiation.)

Return the sum of all numbers Fox Ciel calculated, modulo m.

### Definition

 Class: Powerit Method: calc Parameters: int, int, int Returns: int Method signature: int calc(int n, int k, int m) (be sure your method is public)

### Constraints

-n will be between 1 and 1,000,000, inclusive.
-k will be between 1 and 400, inclusive.
-m will be between 2 and 1,000,000,000, inclusive.

### Examples

0)

 `4` `1` `107`
`Returns: 10`
1)

 `4` `2` `107`
`Returns: 100`
 We have k=2 and therefore (2^k - 1) = (2^2 - 1) = 3. Fox Ciel calculated the numbers 1^3, 2^3, 3^3, and 4^3. Their sum is 100, and 100 modulo 107 is 100.
2)

 `3` `3` `107`
`Returns: 69`
 The actual sum of Ciel's numbers is 2316, and 2316 modulo 107 is 69.
3)

 `1` `400` `107`
`Returns: 1`
4)

 `10` `2` `10`
`Returns: 5`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
Single Round Match 660 Round 1 - Division II, Level Three