시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

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$.

예제 입력 1

1 1024

예제 출력 1

0

예제 입력 2

2 1048

예제 출력 2

1

예제 입력 3

4 11312

예제 출력 3

123

예제 입력 4

4 31415926

예제 출력 4

942

힌트

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