题目描述

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

输入格式

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

输出格式

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

样例

input

7

output

1716

数据范围与提示

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