Description

Input

为一个正整数N（ N <= 1, 000, 000, 000）。

Output

包括一个整数，即将所有点连成多边形的所有可能的数目模1,000,000,000的结果。

Samples

3

8