题目描述

JOHNKRAM 最近在研究集合。他从 $[1, 2n]$ 中任选了 $n$ 个不同的整数，组成了 $\binom{2n}{n}$ 个不同的集合。现在他想知道，在这些集合中，有多少个集合含有偶数个偶数？答案可能很大，你只需要告诉他答案 $\bmod 1000003$ 的结果即可。

输入格式

一行，一个整数 $n$，意思如题所示。

输出格式

一行，一个整数 $\text{ans}$，表示答案 $\bmod 1000003$ 的结果。

样例

输入：

7

输出：

1716

数据范围与提示

对于 $30\%$ 的数据，$n \leq 1000003$；
对于 $100\%$ 的数据，$1 \leq n \leq 10^{18}$。