19284번 - Oneness 다국어

문제

Define oneness of the number $x$ to be a number of integers $d > 1$ dividing $x,ドル whose decimal representation consists only of digit 1ドル$. For example, $oneness(121) = 1$ and $oneness(1221) = 2$.

Number $n$ is obtained using the following algorithm involving a pseudo-random number generator. You are given two integers $l$ and $s_0,ドル which are the length of the decimal representation of $n$ and the generator seed.

The digits $d_0d_1 \ldots d_{l-1}$ of the number $n$ are generated by the following recursions:

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

It is guaranteed that $d_0$ is non-zero.

Calculate the total oneness over all integers between 1ドル$ and $n$.

입력

The first line contains two integers $l,ドル $s$ (1ドル\le l \le 250,000円,ドル 0ドル \leq s_0 < 2^{32}$), the number of digits in the decimal representation of $n$ and the seed of pseudo-random number generator that is used to create the decimal representation of $n$.

출력

Output the sum of oneness over all integers between 1ドル$ and $n$.

제한

힌트

In sample tests $n$ equals 1, 11, 1221 and 9359 respectively.