"Ngày xửa ngày xưa, từ rất lâu rồi, từ khi ông nội của ông nội ta kể cho ông nội ta nghe, tương truyền trong nhân gian rằng, nếu ai đếm được số số may mắn có độ dài ~N~ và có ít nhất ~K~ chữ số ~6~ đứng cạnh nhau thì sẽ không phải chịu kiếp đi cài win dạo mà được làm coder hạnh phúc đến trọn đời"

Nghe lời của bố kể lại, Mew quyết tâm giải bằng được bài toán trên, lần này máy tính quá khủng (Intel Core i10) nhưng lại không cài FPC hay C++ nên Mew đành nhờ các bạn giải hộ.

Input

Gồm 2 số nguyên ~N~ và ~K~

Output

Một số duy nhất là đáp án lấy theo modulo ~10^{9} + 7~.

Giới hạn

• ~30\%~ số test có ~N, K \le 1000~.
• ~20\%~ số test có ~K = 1~
• ~50\%~ còn lại ~N, K \le 100000~

Sample Input

4 3

Sample Output

18

Note

~N = 4~, ~K = 3~, có ~18~ số thỏa mãn: ~1666~, ~2666~, ~3666~, ~4666~, ~5666~, ~6660~, ~6661~, ~6662~, ~6663~, ~6664~, ~6665~, ~6666~, ~6667~, ~6668~, ~6669~, ~7666~, ~8666~, ~9666~.