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<sup class="upper-index">9</sup>, 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.
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.
17 1
12
1000000 2
fca2c
200000000 5
bebc69a
999999 3
f467f
40 1
2a
105 1
6f
200000000 10
bebc200
1 1
1
2 1
2
3 1
3
4 1
4
6 1
6
7 1
7
8 1
8
9 1
9
10 1
a
12 1
c
18 1
13
1167959139 3
4683acbb
100 1
6a
641009859 3
26a9469b
1524125987 8
5ad85123
1000 1
4a3
2000 1
95b
5000 1
19dc
702209411 8
29dadd83
1585325539 3
5fb74be8
1058376259 9
3f158a43
50000 1
13a5b
70000 1
1cb74
90000 1
26eaf
100000 1
2b7d4
1941492387 8
73b8d2a3
1000000 1
256a18
2000000 1
50f4d8
3000000 1
7d90a8
4000000 1
a92d5b
824608515 4
312dc989
900000000 1
2681c493a
1000000000 1
2c40e8619
1300000000 1
3e8d62fa5
1500000000 1
4b1cda965
1700000000 1
57ba24938
1900000000 1
6349ae508
2000000000 1
6a07d23f8
44340 1
fedc
1999999999 1
6a07d23f5
546481140 1
fedcba98
546481139 1
fedcba97
546481138 1
fedcba96
546481137 1
fedcba95
546481136 1
fedcba94
546481135 1
fedcba93
546481134 1
fedcba92
546481141 1
102345678
546481142 1
102345679
546481143 1
10234567a
546481144 1
10234567b
546481145 1
10234567c
546481146 1
10234567d
546481147 1
10234567e
2691939 4
29141a
1802030518 10
6b68cdb6
685146646 10
28d68216
1863230070 5
6f0f3e77
1041313494 5
3e117ed6
219396918 2
ea9f693
1102513046 6
41b70514
1985629174 6
765a4ee7
1458679894 10
56f1b056
341796022 10
145f64b6
1519879446 7
5a97851b
1452405440 3
57b44cc7
200000000 2
d5e0c94
200000000 3
c013b12
200000000 4
bec960c
200000000 6
bebc20b
200000000 7
bebc200
200000000 8
bebc200
200000000 9
bebc200
567234712 4
21d3aa38
385192384 9
16f591c0
574832319 3
22a95637
1500000000 4
59776758
1999999999 2
8e535823
123456789 2
83b4f3b
3544444 8
36157c
234566 10
39446
23444234 8
165bb0a
1000034 1
256a79
324234 5
4f28a
1994456432 4
76f4e197
1234543238 8
4995a286
1988888884 3
7821526a
1933456288 4
7351a5a9
1243123 5
12f7f4
1265 2
4f5
3245457 4
31865a
1999999999 10
773593ff
1988976545 10
768d5fa1
400000 4
61a85
1231234 3
12d4a0
print("_RANDOM_GUESS_1689182385.621214")# 1689182385.621251