Fangy 收集 cookie。有一次,他决定拿一个盒子,用某种方式把饼干放进去。如果我们取一个大小为 k × k 的正方形,分成大小为 1 × 1 的块,并在主对角线和位于其上方的单元格上绘制主对角线,那么绘制的面积将等于一块大小为 k 的饼干所占据的面积。 Fangy 还有一个带有 2n × 2n 方形底座的盒子,分为 1 × 1 大小的块。在盒子里,饼干不应重叠,也不应翻转或旋转。分别参见图中大小为2和4的cookie:
为了堆叠饼干,小海象使用以下算法。他从存储库中取出可以放入盒子中某个位置的最大的饼干并将其放在那里。一切都可以是完美的,但可惜的是,在存储库中,小海象有无限多个尺寸为 2 或更大的饼干,并且没有尺寸为 1 的饼干,因此,空单元格将保留在盒子中。 Fangy 想知道最后会剩下多少个空单元格。
输入
第一行包含一个整数 n (0 ≤ n ≤ 1000)。
输出
打印单个数字,等于框中空单元格的数量。答案应以 106 + 3 为模打印。
示例
输入 #1
3
输出 #1
9
注意
如果盒子的底部尺寸为 23 × 23(如示例所示),则 cookie 将以以下方式放置在那里: