406553: GYM102439 G Sequence exploration

Consider the following numerical sequence which you will explore:

$$$1$$$, $$$11$$$, $$$21$$$, $$$1211$$$, $$$111221$$$, $$$312211$$$, $$$13112221$$$, $$$1113213211$$$...

In this numerical sequence, to get the next number, you need to divide the current one into groups of identical numbers and replace each group with the number of repeated digits and the repeated digit in the group itself (in that order). So, with the number $$$13112221$$$ the following will occur: $$$13112221 \rightarrow 1, 3, 11, 222, 1 \rightarrow 11, 13, 21, 32, 11 \rightarrow 1113213211$$$. It can be seen that this sequence is growing rather rapidly, which makes research very difficult. Fortunately, we can limit ourselves to the last $$$m$$$ digits of the number of this sequence, written in decimal notation, which will allow us to do some research.

Let's start with some simple exploration. Output the last $$$m$$$ digits of the $$$n$$$-th number of the given sequence.

The first line contains two integers $$$n$$$ and $$$m$$$ — the sequence number and the number of the last digits to be output.

$$$$$$1 \le n \le 10^{18}$$$$$$ $$$$$$1 \le m \le 1\,000$$$$$$

In the single line print a single integer — the last $$$m$$$ digits of the $$$n$$$-th number of the sequence. If the length of the $$$n$$$-th number is less than $$$m$$$, then you need to output the number itself.

1 2

1

42 1

1