考虑如下数值序列： 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211...

在该数值序列中，要得到下一个数，你需要将当前的数划分为若干个由相同数字组成的组，并将每一组替换为该组中重复数字的个数以及该数字本身（按此顺序）。例如，对于数字 13112221，将发生如下变化：13112221 → 1, 3, 11, 222, 1 → 11, 13, 21, 32, 11 → 1113213211。可以看出，该序列增长得非常快，这使得研究变得非常困难。幸运的是，我们可以将自己限制在该序列中数字的最后 $m$ 位（以十进制表示），这将允许我们进行一些研究。

让我们从一些简单的探索开始。输出给定序列中第 $n$ 个数的最后 $m$ 位。

输入格式

第一行包含两个整数 $n$ 和 $m$ —— 表示序列的项数以及需要输出的末尾位数。

$1 \le n \le 10^{18}$ $1 \le m \le 1000$

输出格式

在一行中输出一个整数 —— 第 $n$ 个数的最后 $m$ 位。如果第 $n$ 个数的长度小于 $m$，则直接输出该数本身。

样例

样例输入 1

1 2

样例输出 1

1

样例输入 2

42 1

样例输出 2

1