Igor and Interesting Numbers

Igor 喜欢十六进制表示法，并且认为如果十六进制正整数中的每一个数字和每一个字母出现次数不多于 t 次，则这个正整数是有趣的。举个例子，如果 t=3 ，那么整数 13a13322 , aaa , abcdef0123456789 是有趣的，但是数字 aaaa , abababab 和 1000000 是不有趣的。 你的任务是找到第 k 小的对于Igor来说有趣的十六进制数。这个整数不应该包含前导零。

Igor likes hexadecimal notation and considers positive integer in the hexadecimal notation interesting if each digit and each letter in it appears no more than $ t $ times. For example, if $ t=3 $ , then integers 13a13322, aaa, abcdef0123456789 are interesting, but numbers aaaa, abababab and 1000000 are not interesting. Your task is to find the $ k $ -th smallest interesting for Igor integer in the hexadecimal notation. The integer should not contain leading zeros.

The first line contains the two integers $ k $ and $ t $ ( $ 1<=k<=2·10^{9} $ , $ 1<=t<=10 $ ) — the number of the required integer and the maximum number of times some integer or letter can appear in interesting integer. It can be shown that the answer always exists for such constraints.

Print in the hexadecimal notation the only integer that is the $ k $ -th smallest interesting integer for Igor.

17 1

12

1000000 2

fca2c

The first 20 interesting integers if $ t=1 $ : 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, 10, 12, 13, 14, 15. So the answer for the first example equals 12.