Powerit | Topcoder Archive

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

```
4
```
```
1
```
```
107
```
```
Returns: 10
```
```
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.
```
3
```
```
3
```
```
107
```
```
Returns: 69
```
The actual sum of Ciel's numbers is 2316, and 2316 modulo 107 is 69.
```
1
```
```
400
```
```
107
```
```
Returns: 1
```
```
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)2024, Topcoder, Inc. All rights reserved.