Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Cookies

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFangy collects cookies. Once he decided to take a box and put cookies into it in some way. If we take a square *k* × *k* in size, divided into blocks 1 × 1 in size and paint there the main diagonal together with cells, which lie above it, then the painted area will be equal to the area occupied by one cookie *k* in size. Fangy also has a box with a square base 2^{n} × 2^{n}, divided into blocks 1 × 1 in size. In a box the cookies should not overlap, and they should not be turned over or rotated. See cookies of sizes 2 and 4 respectively on the figure:

To stack the cookies the little walrus uses the following algorithm. He takes out of the repository the largest cookie which can fit in some place in the box and puts it there. Everything could be perfect but alas, in the repository the little walrus has infinitely many cookies of size 2 and larger, and there are no cookies of size 1, therefore, empty cells will remain in the box. Fangy wants to know how many empty cells will be left in the end.

Input

The first line contains a single integer *n* (0 ≤ *n* ≤ 1000).

Output

Print the single number, equal to the number of empty cells in the box. The answer should be printed modulo 10^{6} + 3.

Examples

Input

3

Output

9

Note

If the box possesses the base of 2^{3} × 2^{3} (as in the example), then the cookies will be put there in the following manner:

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/20/2019 15:39:57 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|