【说明】

本题不再额外提供样例文件。

【问题描述】

有 N 种神秘物质，第 i 种神秘物质的能量恰好为 i。

你可以任选若干种物质进行能量聚合，这样会产生巨大的能量，得到的能量值为参与聚合的各种物质的能量之积，记为 P。

如果 P 恰好是一个完全平方数，则能量聚合将会产生巨大效能，诞生一种新型物质。

为了使新型物质的能量尽可能大，你想得到的 P 的值尽可能大。

问：你能得到的 P 的值最大可能是多少？

这个数可能很大，你只需要输出其 mod 100000007 的值。

【输入格式】

一个整数 N

【输出格式】

一个整数，表示答案 mod 100000007

【样例1输入】

7

【样例1输出】

144

【样例2输入】

1234567

【样例2输出】

79882433

【数据范围】

20%的数据：$1 ≤ N ≤ 100$。

50%的数据：$1 ≤ N ≤ 5000$。

70%的数据：$1 ≤ N ≤ 10^5$ 。

100%的数据：$1 ≤ N ≤ 5 × 10^6$ 。