Counting Pentagon Points

Interview

Time limit2sMemory limit256 MB

Summary

Compute the total pentagonal points after N steps using a simple arithmetic formula, modulo 45678.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

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.

Examples3

Example 1
Input
```
3
```
Expected output
```
22
```
Example 2
Input
```
1
```
Expected output
```
5
```
Example 3
Input
```
19
```
Expected output
```
590
```