Submit solution


Points: 100.00
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Một xâu được gọi xâu tam phân nếu xâu đó chỉ tồn tại các kí tự 0,1,2. Hãy đếm số lượng xâu tam phân độ dài n mà không có 2 kí tự 1 liền kề nhau.

Dữ liệu

  • Dòng đầu là một số nguyên n (1n105).

Kết quả

  • 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 109+7.

Ví dụ

Sample Input 1
Copy
2
Sample Output 1
Copy
8
Sample Input 2
Copy
10
Sample Output 2
Copy
24960

Giải thích

Trong ví dụ thứ nhất có 8 xâu: 00,01,02,10,12,20,21,22

Nguồn: Beginner Free Contest 30


Comments

Please read the guidelines before commenting.


There are no comments at the moment.