domino3

Tiếp tục là bài toán xếp các quân Domino nhưng dễ hơn so với bài Domino2.
Cho một hộp cờ Domino hình chữ nhật có dạng 2xn, hỏi có bao nhiêu cách xếp các quân cờ Domino vào hộp với điều kiện:

• Phải lấp đầy hộp bằng n quân cờ Domino giống nhau có kích thước 1x2.
• Chỉ xếp thành 1 lớp, tức các quân Domino không được chồng lên nhau.

Hãy tìm và in ra số cách sắp xếp quân cờ vào hộp. Kết quả chia lấy dư cho 109+7.

Ví dụ:

• Với n = 3 thì domino3(n) = 3.
  Giải thích: Ta có tất cả 3 cách xếp như sau:
        
  
  
• Với n = 4 thì domino3(n) = 5.
  Giải thích: Ta có tất cả 5 cách xếp như sau:
  
  
  

Đầu vào/đầu ra:

• [Thời gian chạy]: 0.5s với C++, 3s với Java/C#, 4s với Python/Go/Java Script
• [Đầu vào] Long n
  1 ≤ n ≤ 1018
• [Đầu ra]: Integer
  Số cách xếp Domino, kết quả chia lấy dư cho 109+7.