定义一个数 $x$ 的 $oneness$ 为能够整除 $x$ 且十进制表示仅由数字 $1$ 组成的整数 $d > 1$ 的个数。例如，$oneness(121) = 1$ 且 $oneness(1221) = 2$。

数字 $n$ 通过以下涉及伪随机数生成器的算法获得。给定两个整数 $l$ 和 $s_0$，分别表示 $n$ 的十进制表示长度和生成器种子。

数字 $n$ 的各位数字 $d_0 d_1 \dots d_{l-1}$ 由以下递归式生成：

$$d_i = \lfloor s_i / 1024 \rfloor \pmod{10}$$ $$s_{i+1} = (747796405 s_i - 1403630843) \pmod{2^{32}}$$

保证 $d_0$ 不为零。

计算所有 $1$ 到 $n$ 之间整数的 $oneness$ 之和。

输入格式

第一行包含两个整数 $l, s_0$ ($1 \le l \le 250\,000, 0 \le s_0 < 2^{32}$)，分别表示 $n$ 的十进制表示长度和用于创建 $n$ 的十进制表示的伪随机数生成器种子。

输出格式

输出所有 $1$ 到 $n$ 之间整数的 $oneness$ 之和。

样例

样例输入 1

1 1024

样例输出 1

0

样例输入 2

2 1048

样例输出 2

1

样例输入 3

4 11312

样例输出 3

123

样例输入 4

4 31415926

样例输出 4

942

说明

在样例测试中，$n$ 分别等于 $1, 11, 1221$ 和 $9359$。