乘积受限的等差数列

题目描述

如果一个正整数序列 $A=(A_1,\dots,A_{|A|})$ 满足以下所有条件，就称它是一个好序列：

• $|A|\ge 3$；
• $A$ 是等差数列，即对所有 $1\le i\le |A|-1$ 都有 $A_{i+1}-A_i=A_2-A_1$；
• $A_2-A_1>0$。

求所有元素之积不超过 $N$ 的好序列的个数。

可以证明，在本题的约束下答案不超过 $10^{18}$。

输入格式

一行一个整数 $N$。

输出格式

输出一个整数，表示答案。

120

18

1000000000000000000

1051148114007

数据范围

对于所有测试数据，保证 $1\le N\le 10^{18}$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。