M. Maximum Paths
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a complete binary tree consisting of $$$n$$$ nodes, numbered with integers from $$$1$$$ to $$$n$$$. For each node $$$i \gt 1$$$, its parent is the node numbered $$$\lfloor i/2 \rfloor$$$. Each edge in the tree is labeled with a digit from $$$1$$$ to $$$9$$$.

For each pair of nodes $$$u$$$ and $$$v$$$, let $$$N(u, v)$$$ denote the sum of the digits that can be read on the edges when moving from node $$$u$$$ to node $$$v$$$ along the shortest path $$$p(u, v)$$$. If $$$u = v$$$, then $$$N(u, v) = 0$$$.

For a node $$$v$$$, let's define the set of hanging paths $$$H(v)$$$: these are the paths that include node $$$v$$$ but do not contain its parent (for node $$$1$$$, all paths containing it are considered hanging).

Let $$$M(v)$$$ denote the hanging path $$$p(u, w)$$$ (i.e., $$$p(u, w) \in H(v)$$$), which has the maximum value of $$$N(u, w)$$$. Such a path is referred to as a maximum path.

In this problem, you need to find the maximum path $$$p(u, w) = M(v)$$$ for each node $$$v$$$, sum the corresponding values of $$$N(u, w)$$$, and output the resulting sum for all $$$v$$$.

Input

The input consists of a single line containing two integers $$$n$$$ and $$$seed$$$ ($$$1 \leq n \leq 10^7$$$, $$$0 \leq seed \lt 2^{31}$$$).

The digits written on the edges of the tree are generated using a linear congruential generator. Specifically, a sequence $$$r$$$ is generated as follows: $$$$$$r_1 = seed,$$$$$$ $$$$$$r_i = (1103515245 \cdot r_{i-1} + 12345) \bmod 2^{31}, \quad 2 \leq i \leq n.$$$$$$

Then, for each edge connecting nodes $$$i$$$ and $$$\lfloor i/2 \rfloor$$$, the digit on that edge is computed as $$$$$$a_i = ((r_i \text{\ \texttt{ \gt }}\text{\texttt{ \gt }\ }16)\bmod 9) + 1, \quad 2 \leq i \leq n.$$$$$$

Output

Output a single integer, which is the required sum.

Example
Input
10 2017
Output
102915
Note

The drawing below illustrates the tree generated by the sample input.

The values of $$$N(u, w)$$$ for the maximum paths $$$M(v)$$$ are as follows: $$$95796$$$, $$$6974$$$, $$$98$$$, $$$41$$$, $$$6$$$, $$$0$$$, $$$0$$$, $$$0$$$, $$$0$$$, $$$0$$$. The sum of these values is $$$102915$$$.