linedUp

Trong một cuộc giao lưu giữa ba công ty A,B và C. Hải muốn sắp xếp cho những của ba công ty ngồi trên một dãy ghế đánh số từ 1->n.

Để tiện cho những người của các công ty giao lưu làm quen với nhau nên Hải đã đưa ra các điều kiện khi xếp dãy ghế như sau:

• Người của công ty C không muốn ngồi ở ghế có số thứ tử lẻ.
• Người cùng chung công ty sẽ không ngồi kế nhau.

Hãy đưa ra số các khác nhau để sắp xếp chỗ ngồi cho những người của các công ty trên dãy n ghế.

Hai các được gọi là khác nhau nếu có một giá trị ở vị trí của cách sắp xếp này khác với các sắp xếp khác.

Ví dụ:

• Với n=3, thì linedUp(n) = 6.
  Giải thích: Có thể xếp được 6 cách như hình dưới:
  
• Với n = 2, thì linedUp(n) = 4.

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

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.

• [Đầu vào] Integer n
  1 ≤ n ≤ 30.

• [Đầu ra] Integer
  Số cách sắp xếp.