ArchLord

All these hard problems made XORin mind-bogglingly hungry. Consequently, he decided to step outside and buy some cake dough for his friends at Take Off Labs, and himself.

However, on his way there, one of his shoelaces managed to untie itself, so now he has to tie it back together.

XORin defines tying his shoe correctly as follows: his shoe has two paralel columns of N holes each. Having an infinite shoelace, a correct tying has the next two properties:

  • The shoelace connects at least one hole from the left side column and one hole from the right side column (so the shoe is properly fastened)
  • No hole is connected more than once. However, some holes may remain disconnected.

After managing to find one suitable solution, XORin's mind wandered towards questions not even he could answer:

How many ways of correctly tying the shoe are there, considering that the order of the connected holes is relevant?

Your task is to find the answer to this question, mod 666013 (where a mod b is the remainder of the division a/b).

Input

A single integer N on the only line, the number of holes on each side of the shoe.

Output

A single integer - the answer to the question, mod 666013.

Constraints

  • 1 ≤ N < 4⋅106

Sample

InputOutputExplanation
256If the left side holes are 1 2 and the right side holes are 3 4, the solutions are:
1-3 3-1
1-4 4-1
2-3 3-2
2-4 4-2
1-2-3 1-3-2 2-3-1 2-1-3 3-1-2 3-2-1
1-2-4 1-4-2 2-4-1 2-1-4 4-1-2 4-2-1
1-3-4 1-4-3 3-4-1 3-1-4 4-1-3 4-3-1
2-3-4 2-4-3 3-4-2 3-2-4 4-2-3 4-3-2
1-2-3-4 1-2-4-3 1-3-2-4 1-3-4-2 1-4-2-3 1-4-3-2
2-1-3-4 2-1-4-3 2-3-1-4 2-3-4-1 2-4-1-3 2-4-3-1
3-1-2-4 3-1-4-2 3-2-1-4 3-2-4-1 3-4-1-2 3-4-2-1
4-1-2-3 4-1-3-2 4-2-1-3 4-2-3-1 4-3-1-2 4-3-2-1
31926
666666280025
Questions?

Sponsors Gold