【题目描述】

学校组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

有 N 根火柴，需要把它们分成若干堆（至少两堆）。问：如何划分，可以使得每一堆火柴的数量之积最大？选手只需要回答最大乘积是多少。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

当 N=4 时会有以下几种分法：

1. {1, 3};

2. {2, 2};

3. {1, 1, 2};

4. {1, 1, 1, 1}

其中 2×2=4 乘积最大。

现在，请你帮助你的好朋友 XZ 设计一个程序，求得正确的答案。

【输入格式】

程序的输入共有一行，一个整数 N

【输出格式】

相对于输入，应输出所求得的最大乘积（一个自然数）。这个值可能很大，你只需要输出其 mod 2,000,000,000,000,000,003 的值。

【样例输入】

7

【样例输出】

12

【样例解释】

N=7 的分法有：

{2, 5}; {3, 4}; {1, 1, 5}; {1, 2, 4}; ……

其中3×4=12 乘积最大。

【数据范围】

20%的数据：2 ≤ n ≤ 20。

50%的数据：2 ≤ n ≤ 100。

100%的数据：2 ≤ n ≤ 100000。