F. [Algo Beat Contest 009 & MROI Round 1] ERESHKIGAL

埃列什基伽勒给了你一个正奇数 ，定义序列 ，其中 ，而 是满足 的最小正整数。她想让你计算以下和式：

输入一个正奇数 。

输出一个正整数 ，表示答案。
由于答案可能较大，所以请对 取模。

输入 #1

3

输出 #1

1

输入 #2

5

输出 #2

9

【样例 1 解释】

当 时，，计算得：

【样例 2 解释】

当 时，，计算得：

【数据范围】

本题采用捆绑测试，只有通过一个 Subtask 中所有的测试点你才能获得对应的分值。