Xâu 012
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Xâu 012 là xâu chỉ gồm các kí tự 0, 1 và 2. Hãy đếm xem có bao nhiêu xâu 012 có độ dài ~n~ mà không có 2 kí tự 1 liền nhau.
Input
- Dòng đầu là một số nguyên ~n~ (~1 \leq n \leq 10^5~)
Output
- In ra một dòng là số lượng xâu thoả mãn. Kết quả có thể lớn, hãy đưa ra kết quả theo phần dư của ~10^9 + 7~.
Sample input 1
2
10
Sample output 1
8
24960
Notes
- Trong ví dụ thứ nhất có 8 xâu: 00, 01, 02, 10, 12, 20, 21, 22
Bình luận
sample input: 2 8
8 3344