33OJ
登录 注册

#P17747. 「RSOI-1D」游戏 / game

「RSOI-1D」游戏 / game

背景

题目来源:【HT-121-Div.3】核桃 CSP-J 组模拟赛

题目描述

小 R 正在跟他的朋友们举行一场报数游戏!

报数游戏的规则是“根号递降”。我们给定一个正整数 xx,要求玩家所报的第一个数必须是 xx。随后,玩家需要不停报数。所报的每个数都必须是正整数,且严格小于前一个数,但其平方必须大于前一个数。

例如,如果玩家报了 55,则接下来报的数只能是 33 或 44;如果玩家报了 99,则接下来报的数只能是 44、55、66、77 或 88。

玩家需要不停报数,直到报出 22 为止。之所以在报出 22 时停止,是因为在报出 22 后,接下来将不再有符合条件的数可报。

在给定 xx 的情况下,玩家一共有多少种报数方法?两种报数方法不同,当且仅当所报数的数量不同,或者存在 ii 使得两种方法所报第 ii 个数不相等。

由于答案可能过大,请将答案对 109+710^9 + 7 取模。

输入格式

输入共一行,包含一个正整数 xx,表示所报的第一个数。

输出格式

输出共一行,输出一个整数,表示玩家的报数方法数量,答案对 109+710^9 + 7 取模。

5
2
9
31
20014
864452326

提示

【样例解释 #1】

所有的报数方法有:[5,3,2][5, 3, 2]、[5,4,3,2][5, 4, 3, 2]。共 22 种。

【样例解释 #2】

所有的报数方法有:[9,4,3,2][9, 4, 3, 2]、[9,5,3,2][9, 5, 3, 2]、[9,5,4,3,2][9, 5, 4, 3, 2]、[9,6,3,2][9, 6, 3, 2]、[9,6,4,3,2][9, 6, 4, 3, 2]、[9,6,5,3,2][9, 6, 5, 3, 2]、[9,6,5,4,3,2][9, 6, 5, 4, 3, 2]、[9,7,3,2][9, 7, 3, 2]、[9,7,4,3,2][9, 7, 4, 3, 2]、[9,7,5,3,2][9, 7, 5, 3, 2]、[9,7,5,4,3,2][9, 7, 5, 4, 3, 2]、[9,7,6,3,2][9, 7, 6, 3, 2]、[9,7,6,4,3,2][9, 7, 6, 4, 3, 2]、[9,7,6,5,3,2][9, 7, 6, 5, 3, 2]、[9,7,6,5,4,3,2][9, 7, 6, 5, 4, 3, 2]、[9,8,3,2][9, 8, 3, 2]、[9,8,4,3,2][9, 8, 4, 3, 2]、[9,8,5,3,2][9, 8, 5, 3, 2]、[9,8,5,4,3,2][9, 8, 5, 4, 3, 2]、[9,8,6,3,2][9, 8, 6, 3, 2]、[9,8,6,4,3,2][9, 8, 6, 4, 3, 2]、[9,8,6,5,3,2][9, 8, 6, 5, 3, 2]、[9,8,6,5,4,3,2][9, 8, 6, 5, 4, 3, 2]、[9,8,7,3,2][9, 8, 7, 3, 2]、[9,8,7,4,3,2][9, 8, 7, 4, 3, 2]、[9,8,7,5,3,2][9, 8, 7, 5, 3, 2]、[9,8,7,5,4,3,2][9, 8, 7, 5, 4, 3, 2]、[9,8,7,6,3,2][9, 8, 7, 6, 3, 2]、[9,8,7,6,4,3,2][9, 8, 7, 6, 4, 3, 2]、[9,8,7,6,5,3,2][9, 8, 7, 6, 5, 3, 2]、[9,8,7,6,5,4,3,2][9, 8, 7, 6, 5, 4, 3, 2]。共 3131 种。

【数据范围】

对于所有测试数据,保证:2≤x≤10122 \le x \le 10^{12}。

::cute-table{tuack} | 测试点编号 | x≤x \le | 特殊性质 | |:-------------------:|:------------:|:----:| | 11 | 22 | 无 | | 22 | 2020 | 无 | | 3∼63 \sim 6 | 10310^3 | 无 | | 7∼97\sim 9 | 10610^6 | 无 | | 1010 | 10610^6 | A | | 11∼1311 \sim 13 | 10910^9 | 无 | | 1414 | 10910^9 | A | | 15∼1815 \sim 18 | 101210^{12} | 无 | | 19∼2019 \sim 20 | 101210^{12} | A |

特殊性质 A:xx 为完全平方数。