Bloom

Hiranmoy Ada Lovelace National Gir...
Limits 800ms, 64 MB

"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 ithi_{th} step will be called Bloom-i.

To create Bloom-i(ii>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 ( π=3.141592653589793238\pi = 3.141592653589793238…).

Input

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

Output

Print how many units of ink will be required.

Samples

InputOutput
1
2
InputOutput
2
16
InputOutput
3
104
InputOutput
6
23296

Submit

Login to submit.

Statistics

89% Solution Ratio
naeem4265Earliest, 2M ago
steinumFastest, 0.0s
steinumLightest, 5.5 kB
TernaryRootedTreeShortest, 431B
Toph uses cookies. By continuing you agree to our Cookie Policy.