题目描述

Fangy 收集饼干。他曾决定拿一个盒子并通过某种方法把饼干放进去。如果我们取一个分割成 $1\times 1$ 的正方形的 $k\times k$ 大小的正方形，并且将主对角线涂色，则涂色的正方形将放入饼干。Fangy 还有一个 $2^n\times 2^n$ 的正方形盒子，并且分割成 $1\times 1$ 的小正方形。盒子里的饼干不可以重叠、旋转或者翻转。下面是大小为 $2,4$ 的饼干：

为了叠放饼干，小海狮使用了下述的算法。他把最大的饼干放在盒子里的合适位置。它有无数块大小大于 $2$ 的饼干，但却没有大小为 $1$ 的饼干。因此会有剩余的格子。Fangy 想要知道会有多少空的格子。

输入格式

输入包括一行，仅有一个单独的整数 $n\ (0\le n\le 1000)$。

输出格式

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

3

9

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