Giải bài trực tuyến

Consider a regular grid of 3 × N points. Every point in the grid has up to eight neighboring points (see figure 1).

Figure 1: Neighboring points (marked by arrows).

We are interested in counting the number of different ways to connect the points of the grid to form a polygon that fulfils the following conditions: 1. The set of vertices of the polygon consists of all 3 × N points. 2. Adjacent vertices of the polygon are neighboring points in the grid. 3. Each polygon is simple, i.e. there must not be any self-intersections. Two possible polygons for N = 6 are given in the figure 2.

Figure 2: Two possible connections of points for N = 6.

Write a program that calculates for a given N the number of possible ways to connect the points as described modulo 1,000,000,000.

Input

The first and only line contains one positive integer N (N <= 1,000,000,000).

Output

The only line to be written contains the remainder of the number of ways to connect the points modulo 1,000,000,000.

Example

Input:
3

Output:
8

Input:
4

Output:
40