Submit solution
Points:
0.73 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem source:
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