Tết đến xuân về, Tũn sang nhà người bác của mình để chúc tết. Những lời chúc sâu sắc của Tũn đã khiến bác mình cảm thấy thích thú và quyết định sẽ lì xì cho cậu. Tuy nhiên để thử thách Tũn, bác đã cầm một tờ tiền polime trên tay và nói với Tũn như sau:
"Trên tay bác đang là một tờ polime, bác sẽ cho cháu một số nguyên dương ~n~. Nhiệm vụ của cháu là cho bác một dãy số gồm ~n~ chữ số, bác sẽ đọc dãy số đó từ trái sang phải, nếu gặp các chữ số 1
, 5
, 9
, tờ tiền hiện tại sẽ chuyển thành tiền giấy. Số 0
là số yêu thích của bác nên nếu gặp nó tờ tiền hiện tại sẽ chuyển thành polime, kể cả các chữ số 0
đứng đầu vô nghĩa bác vẫn tính. Nếu gặp chữ số 7
hoặc 8
tờ tiền hiện tại sẽ được chuyển thành chất liệu ngược lại. Dãy số mà cháu chọn sẽ quyết định phần thưởng mà cháu nhận!"
Tũn thầm nghĩ thật quá đơn giản để đưa một dãy số giúp mình nhận được lì xì polime, vì vậy Tũn muốn biết mình có bao nhiêu cách để đưa ra được dãy số như thế. Bạn có thể trả lời giúp Tũn không?
Dữ liệu vào
- Một số nguyên dương ~n~ duy nhất ~(n \le 10^9)~ là số chữ số yêu cầu.
Kết quả
- Một số nguyên nhất là đáp án cho câu hỏi của Tũn sau khi chia lấy dư cho ~1000000007~.
Giới hạn
- Có ~20\%~ số test ứng với ~20\%~ số điểm có ~n \le 6~.
- Có ~60\%~ số test ứng với ~60\%~ số điểm có ~n \le 10^6~.
- ~20\%~ số test còn lại không có ràng buộc gì thêm.
Ví dụ
Dữ liệu
1
Kết quả
5
Giải thích
- Các dãy số gồm ~1~ chữ số thỏa mãn là:
0
,2
,3
,4
,6
Bình luận