Question

[Doãn Thị Thanh Bình]

Có một khoảng sân hình chữ nhật kích thước $2\times n$ ô vuông, gồm $2$ hàng và $n$ cột. Đánh số hàng từ $1$ đến $2$ theo thứ tự từ trên xuống dưới, đánh số cột từ $1$ đến $n$ theo thứ tự từ trái qua phải. Người ta muốn lát sân bằng gạch màu trắng và điểm xuyết một số ô gạch màu đen, mỗi ô vuông được lát bởi một viên gạch, sao cho không có hai viên gạch màu đen nào chung cạnh với nhau.

Yêu cầu: Hỏi có tất cả bao nhiêu cách khác nhau để lát khoảng sân trên (hai cách lát sân được gọi là khác nhau nếu tồn tại tối thiểu một ô ở dòng $i$ cột $j$ được lát gạch màu trắng ở cách này và lát gạch màu đen ở cách kia). Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư sau khi chia cho $10^8$.