Bloom

"DALL·E 36FC" is a new AI system that can create realistic images and art from a description in natural language.

OpenAI innovates a new design to beautify art-work. Which increases the beauty of the art-work many times. This design is created through a specific pattern. Pattern creation can be divided into several steps. In the first step a circle will be created and its name will be Bloom-1. Similarly, the circles formed in the $i_{th}$ step will be called Bloom-i.

To create Bloom-i($i$>1) circles the following procedure will be followed:

1. The radius of all Bloom-i circles will be exactly half the radius of Bloom-(i-1).

2. Bloom-i circles must touch both the center and the circumference of a Bloom-(i-1) circle.

3. The circumference of a Bloom-i circle must touch the center of at least 2 Bloom-i circles and these 3 circles must be generated for the same Bloom-(i-1) circle.

Note that, a Bloom-i circle will produce exactly 6 bloom-(i+1) circles and if 2 Bloom-(i+1) circles created for 2 different Bloom-i overlap completely, those 2 Bloom-(i+ 1) circle will be treated separately.

To maintain the beauty of all circles, OpenAI will adjust the radius of Bloom-1 so that all circles drawn later have integer radius. OpenAI wants to draw circles up to Bloom-n. Since the art needs to be printed later, OpenAI wants to know the minimum number of units of ink needed to print. 1 unit of ink will be required to print 1 meter.

Since the number can come as a fraction and much larger, it must be expressed as mod 4294967291 after dividing by $\pi$ ( $\pi = 3.141592653589793238…$).

Input

The only line contains the integer $n$($0 \le n \le 10^{15}$)

Output

Print how many units of ink will be required.

Samples

Input	Output
1	2

Input	Output
2	16

Input	Output
3	104

Input	Output
6	23296