0198. Simple Calculations

Input file name:	calc.in
Output file name:	calc.out
Time limit:	500 ms
Memory limit:	32 megabytes

You have to calculate the function F(n,k) = (2²ⁿ + 1) mod k.

Input file

Input file contains two integer numbers n and k separated by spaces (0 ≤ n ≤ 2³¹-1, 1 ≤ k ≤ 10⁶).

Output file

You must output F(n,k).

Examples:

calc.in	calc.out
0 4	3

Source: Petrozavodsk Summer 2003. Saratov SU Contest, Wednesday, August 27

Discuss       Submit a solution