#1103. TABLE

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một bảng gồm hai dòng và N cột. Hai ô được gọi là kề nếu chúng có chung một cạnh.

Yêu cầu: Hãy viết chương trình tính số bảng khác nhau có thế thu được nếu ta tô màu đen một hoặc nhiều ô trong bảng và các ô được tô đôi một không kề nhau.

Dữ liệu vào:

  • Một dòng duy nhất chứa số nguyên dương N (N≤10^{18}) .

Dữ liệu ra:

  • Ghi ra một số duy nhất là kết quả bài toán lấy theo modul 12345678 .

Ví dụ:

Dữ liệu vào:
2
Dữ liệu ra:
6
Giải thích:
Hình minh họa cho test đề bài