Packaging machine#2948

Packaging machine

1 second

64 megabytes

Easy

In a packaging machine, there are $n$ toy Santa Clauses and $n$ Snow Maidens. The machine can create packages in the following ways:

One Santa Claus in one of two different types of packages;
One Snow Maiden;
A Santa Claus and a Snow Maiden together in one package.

After all the toys are packaged, the machine will produce a sequence of packages of $4$ different types. How many distinct sequences of packages can the machine produce?

Input

The first line of the input contains an integer $n$ ( $1 \leq n \leq 1 0^{6}$ 1 \leq n \leq 10^6).

Output

Output a single integer — the number of different packaging sequences, calculated modulo $1000003$ .

Examples

Example 1

Loading

1 \leq n \leq 1 0^{6}