背景
题目来源:【HT-121-Div.3】核桃 CSP-J 组模拟赛
题目描述
小 R 正在跟他的朋友们举行一场报数游戏!
报数游戏的规则是“根号递降”。我们给定一个正整数 x,要求玩家所报的第一个数必须是 x。随后,玩家需要不停报数。所报的每个数都必须是正整数,且严格小于前一个数,但其平方必须大于前一个数。
例如,如果玩家报了 5,则接下来报的数只能是 3 或 4;如果玩家报了 9,则接下来报的数只能是 4、5、6、7 或 8。
玩家需要不停报数,直到报出 2 为止。之所以在报出 2 时停止,是因为在报出 2 后,接下来将不再有符合条件的数可报。
在给定 x 的情况下,玩家一共有多少种报数方法?两种报数方法不同,当且仅当所报数的数量不同,或者存在 i 使得两种方法所报第 i 个数不相等。
由于答案可能过大,请将答案对 109+7 取模。
输入格式
输入共一行,包含一个正整数 x,表示所报的第一个数。
输出格式
输出共一行,输出一个整数,表示玩家的报数方法数量,答案对 109+7 取模。
5
2
9
31
20014
864452326
提示
【样例解释 #1】
所有的报数方法有:[5,3,2]、[5,4,3,2]。共 2 种。
【样例解释 #2】
所有的报数方法有:[9,4,3,2]、[9,5,3,2]、[9,5,4,3,2]、[9,6,3,2]、[9,6,4,3,2]、[9,6,5,3,2]、[9,6,5,4,3,2]、[9,7,3,2]、[9,7,4,3,2]、[9,7,5,3,2]、[9,7,5,4,3,2]、[9,7,6,3,2]、[9,7,6,4,3,2]、[9,7,6,5,3,2]、[9,7,6,5,4,3,2]、[9,8,3,2]、[9,8,4,3,2]、[9,8,5,3,2]、[9,8,5,4,3,2]、[9,8,6,3,2]、[9,8,6,4,3,2]、[9,8,6,5,3,2]、[9,8,6,5,4,3,2]、[9,8,7,3,2]、[9,8,7,4,3,2]、[9,8,7,5,3,2]、[9,8,7,5,4,3,2]、[9,8,7,6,3,2]、[9,8,7,6,4,3,2]、[9,8,7,6,5,3,2]、[9,8,7,6,5,4,3,2]。共 31 种。
【数据范围】
对于所有测试数据,保证:2≤x≤1012。
::cute-table{tuack}
| 测试点编号 | x≤ | 特殊性质 |
|:-------------------:|:------------:|:----:|
| 1 | 2 | 无 |
| 2 | 20 | 无 |
| 3∼6 | 103 | 无 |
| 7∼9 | 106 | 无 |
| 10 | 106 | A |
| 11∼13 | 109 | 无 |
| 14 | 109 | A |
| 15∼18 | 1012 | 无 |
| 19∼20 | 1012 | A |
特殊性质 A:x 为完全平方数。