### PROBLEM LINK:

### DIFFICULTY:

EASY

### PREREQUISITES:

High school maths

### PROBLEM:

Calculate **(2 ^{N__bin})^{2} % 1000000007** for given

**N**, where N__bin stands for the decimal number encoded by the representation in base 2 of the number N

### QUICK EXPLANATION:

Store the binary representation of N as decimal number in appropriate data type(as per language). Use fast exponentiation technique to calculate the result within time limit.

### EXPLANATION:

First task is to get binary representation of N as decimal number. The largest value of N is 600000 whose binary representation is 10010010011111000000 which is less than 2^64 but greater than 2^63. For C programmers, unsigned long long is suitable to store this value.

Next task is to calculate (2^{N_bin})^{2} % 1000000007 within time limit. This can be achieved using Right-to-left binary method for modular exponentiation.

See mugurelionut’s solution for simple implementation in C/C++

Another simple way of calculating 2^{n} in log n time is by using exponentiation by squaring. See setter’s solution for a simple function using this technique.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here

Tester’s solution can be found here and here