CF70A.Cookies

Fangy 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.

方阳收集饼干。有一天，他决定拿一个盒子，并以某种方式将饼干放入其中。如果我们取一个大小为 $k \times k$ 的正方形，将其划分为 $1 \times 1$ 的小方格，并将主对角线及其上方的所有方格涂色，则涂色区域的面积就等于一块大小为 $k$ 的饼干所占据的面积。方阳还有一个底面为 $2^n \times 2^n$ 的正方形盒子，该盒子也被划分为 $1 \times 1$ 的小方格。在盒子中，饼干不能重叠，也不能翻转或旋转。图中分别展示了大小为 $2$ 和 $4$ 的饼干：

为了堆叠饼干，小海象采用如下算法：他从仓库中取出当前能放进盒子某个空位的最大尺寸的饼干，并将其放入该位置。一切本应完美，但不幸的是，仓库中只有无穷多个尺寸为 $2$ 及更大的饼干，而没有尺寸为 $1$ 的饼干，因此盒子中最终会留下一些空单元格。方阳想知道最后会剩下多少个空单元格。

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

第一行包含一个整数 $n$（$0 \leq n \leq 1000$）。

Print the single number, equal to the number of empty cells in the box. The answer should be printed modulo 106 + 3.

输出单个数字，该数字等于盒子中空单元格的数量。答案需对 $10^6 + 3$ 取模后输出。

If the box possesses the base of 23 × 23 (as in the example), then the cookies will be put there in the following manner:

如果盒子的底面为 $23 \times 23$（如示例所示），则饼干将按如下方式放置：