JOIN
Get Time

   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