Cookies

【题目描述】 Fangy收集饼干。他曾决定拿一个盒子并通过某种方法把饼干放进去。如果我们取一个分割成$1\times 1$的正方形的$k\times k$大小的正方形，并且将主对角线涂色，则涂色的正方形将放入饼干。Fangy还有一个$2^n\times 2^n$的正方形盒子，并且分割成$1\times 1$的小正方形。盒子里的饼干不可以重叠、旋转或者翻转。下面是大小为$2,4$的饼干：  为了叠放饼干，小海狮使用了下述的算法。他把最大的饼干放在盒子里的合适位置。它有无数块大小大于$2$的饼干，但却没有大小为$1$的饼干。因此会有剩余的格子。Fangy想要知道会有多少空的格子。 【输入格式】 输入包括一行，仅有一个单独的整数$n(0<=n<=1000)$。 【输出格式】 输出一个数，它与剩余格子数量等同。答案应该对$10^6+3$取模。 【说明/提示】 如果盒子是$2^3\times 2^3$（就像样例中的），饼干就会按照如下方式摆放： 

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.

The first line contains a single integer $ n $ ( $ 0<=n<=1000 $ ).

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

3

9

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: