Practice Memoization and Recursion with the exercise "The G Note"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Memoization
Recursion
Arrays
Polynomials
Mathematics

Statement

Goal

This puzzle is related to Ada Lovelace's G Note.

Compute S_N = (0^N + 1^N + 2^N + ... + (N^N)^N) mod M with M = 2^53.

Examples

S_2 = (0^2 + 1^2 + 2^2 + 3^2 + 4^2) mod 2^53 = 30
S_4 = (0^4 + 1^4 + 2^4 + ... + 256^4) mod 2^53 = 222055401600
S_5 = 155369480450947265625 mod 2^53 = 4300505919894617

Note

For N=513, (513^513)^513 is an integer on the order of 1E713210.
It might be worth considering avoiding actually computing it.

Input

An integer N.

Output

The integer S_N (mod 2^53).

Constraints

0 ≤ N ≤ 513

Example

Input

Output

4300505919894617

Solve it

A higher resolution is required to access the IDE