题目描述

反向排列与原来一样的数我们称之为回文数。例如：12321、123321 等都是回文数，而

1232、1231、12322 等都不是回文数。

如果一个数 P 从左到右可以拆分成三个不同的不小于 100 的回文数 x、y、z，x<y<z并 且 x+y+z 的值不大于 n，则我们称 P 为超越回文数。

如果在 x 和 y 中间及 y 和 z 之间插入一 个“$”符号，形成的新的字符串，我们称之为“超越回文串”。 例如：n=400,则 x=101111121 为一个超越回文数，因为 x 可以拆分成 101、111、121 三 个回文数，且 101<111<121,101+111+121=334<400，符合超越回文数的定义。

如果我们在 101 和 111 之间及 111 和 121 之间各插入一个“$”，则会形成一个新串 “101$111$121”，它就是我们所讲的“超越回文串”。

现在告诉你 n 的值，你能求出不同的“超越回文串”的数量么？

输入格式

第一行输入一个数字 n，n<=5*1000000

输出格式

输出一行一个整数表示该条件下的不同的“超越回文串”的数量。

350

2

</p>

提示

【样例 1 说明】

该条件下的超越回文串为：101$111$121、101$111$131,共 2 个。

【数据范围】

对于 20% 的数据，满足 n≤3000；

对于 40% 的数据，满足 n<=100000

对于 100% 的数据，满足 1 ≤ n ≤ 5*10⁶

来源

2023年六年级集训队选拔测