等比数列三角形
题号：NC25520
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

求三边都是 的整数，且成等比数列的三角形个数。
由于答案可能很大，所以你要把答案对 取模后输出。
注：本题在oeis上搜过了，搜不到的……

输入描述:

一行一个整数 n

输出描述:

一行一个整数表示答案
示例1

输入

复制 
9

输出

复制 
10

说明

除去 9 个等边三角形，还有 {4, 6, 9} 。

备注:

数据范围