Elastic Collisions

Time limit3sMemory limit256 MB

Summary

Two bodies on a line, mass 1 at rest and mass N^2 approaching, bounce elastically between each other and a wall; count the total collisions before both move right forever.

Level: Medium7 of 10
Topics: Simulation, Math, Implementation, Number theory
Solved: No attempts yet

Problem

An elastic collision is a collision in which kinetic energy is conserved. On a line, two bodies with masses $m_1$ and $m_2$ move with velocities (here velocity includes direction) $u_1$ and $u_2$ and collide elastically; after the collision their velocities are

$v_1 = \frac{m_1-m_2}{m_1+m_2}u_1 + \frac{2m_2}{m_1+m_2}u_2$

$v_2 = \frac{2m_1}{m_1+m_2}u_1 - \frac{m_1-m_2}{m_1+m_2}u_2$

For example, if a body of mass $2m$ approaches from the left with velocity $v$ and a body of mass $m$ approaches from the right with velocity $-v$ , then after the elastic collision their velocities are $-v/3$ and $5v/3$ . Here the sign of a velocity is positive when the body moves from left to right. When a body collides elastically with a stationary wall, the body's speed stays the same and only its direction reverses, so only the sign of the velocity changes.

Now consider two bodies $A$ and $B$ moving on a line whose left end is blocked by a wall, as in the figure below. The mass of $A$ is 1 and it is initially at rest. The mass of $B$ is $N^2$ and it initially approaches from the right of $A$ . How many collisions occur in total (counting both collisions between $A$ and $B$ and collisions between the wall and $A$ )? Ignore all friction, and all collisions are elastic.

Input

The first line contains a positive integer $N$ . (1 ≤ $N$ ≤ 500)

Output

Print the total number of collisions.

Hint

Using Python's fractions module is strongly recommended.

Examples3

Example 1
Input
```
1
```
Expected output
```
3
```
Example 2
Input
```
7
```
Expected output
```
22
```
Example 3
Input
```
113
```
Expected output
```
355
```