Migrated from Lutece 2842 致十年以后的我，现在的你猜的是什么数？

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

10年後の私へ 致十年以后的我

今は幸せでしょうか 现在的你感到幸福么？

---

致十年以后的我：

现在的你感到幸福么？

还是正沉浸在悲伤中

默默地流着泪？

不过在你的身旁

依然会有不变的存在

未能察觉到你

依然在被守护者吧

---

我在你十年前的现在写下了一个数字 $x\ (0\le x<2^n)$ ——是秘密哦！

但现在的你，应该能够猜出这个数吧——

你可以每次询问一个数 $t$，我会穿越到未来告诉你 $t~\texttt{AND}\ x$ 是否等于 $t$ ——$\texttt{AND}$ 是按位与运算。

不过，只有等你所有询问完毕后我才会来告诉你。

时间紧迫，你需要构造出最少的询问次数来猜出这个数字。

那么，你有多少种方案能猜出数字呢？

并且，这个方案数要对 $10^6+3$ 取模。

约定好了哦！

Input

一行一个整数 $n\ (0\le n\le 10^9)$。

Output

输出一行一个整数，表示具有最少询问次数的方案数对 $10^6+3$ 取模后的结果。

Samples

3

6

Resources

The 18th UESTC Programming Contest Preliminary