Counting Pentagon Points

Time limit

Memory limit

256 MB

Problem

A pentagon pattern is expanded step by step while points are placed along its sides. Step 1 has 5 points. From step 2 onward, step N adds 3N + 1 new points compared with the previous step. Therefore step 2 adds 7 points, and step 3 adds 10 points.

Given an integer N, find the number of points at step N.

Input

The first line contains an integer N.

1 <= N <= 10,000,000

Output

Print the number of points at step N modulo 45678.