Lucky Number

View as PDF

Submit solution

Points: 0.73 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Ðề thi chọn đội tuyển Hải Phòng
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

"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~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.