CF70A Cookies

Fangy收集饼干。他曾决定拿一个盒子并通过某种方法把饼干放进去。如果我们取一个分割成$1\times 1$的小正方形的$k\times k$大小的正方形饼干，并且将主对角线涂色，则涂色部分的小正方形将放入盒子。Fangy还有一个$2^n\times 2^n$的正方形盒子，并且分割成$1\times 1$的小正方形。盒子里的饼干不可以重叠、旋转或者翻转。下面是大小为$2,4$的饼干：  为了叠放饼干，小海狮使用了下述的算法。他把最大的饼干放在盒子里的合适位置。它有无数块大小大于$2$的饼干，但却没有大小为$1$的饼干。因此会有剩余的格子。Fangy想要知道会有多少空的格子。

输入包括一行，仅有一个单独的整数$n(0

输出一个数，它与剩余格子数量等同。答案应该对$10^6+3$取模。

如果盒子是$2^3\times 2^3$（就像样例中的），饼干就会按照如下方式摆放：