There are some imposustor among sus

Among sus là một trò chơi rất thú vị mà bạn có thể chơi với bạn bè. Về cơ bản thì trò chơi này cũng không khác werewolf là mấy. Các bạn sẽ ở trong 1 con tàu và sẽ có một vài người là imposustor - kẻ giả mạo sẽ tìm mọi cách để sát hại người khác hay phá hoại, crewmate - người thường sẽ phải hoàn thành nhiệm vụ và tìm ra imposustor trong quá trình sửa chữa con tàu. Crewmate sẽ chiến thắng nếu hoàn thành hết nhiệm vụ hoặc tìm ra hết imposustor, còn imposustor sẽ thắng khi số imposustor ít hơn hoặc bằng so với số crewmate hay là họ phá hủy con tàu thành công.

Trong thời gian nghỉ hè, huyhau6a2 vì đã quá chán với những trò chơi như Free Fire, Liên Quân Mobile, Osu, Geometry Dash, ... nên cậu quyết định tìm một trò chơi mới đủ thú vị và có thể chơi cùng bạn bè. Ngày đó cũng như ngày thường, cậu vào Google Play lướt tìm trò chơi và đã tìm thấy tựa game Among sus. Sau khi nghiên cứu và coi những video ~~của mấy ông Ấn Độ~~ chơi trên youtube thì cậu đã cảm thấy trò này rất thú vị. Thế là cậu đã dựa vào quan hệ bạn bè gần xa, bà con cuối phố. Và cậu đã rủ được $n-1$ người khác cùng chơi trò này, cộng thêm cậu nữa thì tổng cộng $n$ người.

Sau khi chơi với những người bạn của cậu được một thời gian, huyhau6a2 bỗng nảy ra một bài toán mới. Nhưng sau khi suy nghĩ xong, vì quá lười + cậu đã nghiện game Among sus rồi nên cậu đành nhường lại cho các bạn. Bài toán như sau:

Giả sử các bạn chơi trò chơi này trên bàn gồm $n$ người. Người thứ $i\ (1\le i\le n)$ sẽ ở cạnh người $i-1$ và người $i+1$ (người thứ nhất chỉ ở cạnh người thứ hai và người thứ $n$ chỉ ở cạnh người thứ $n-1$). Mỗi người trong trò chơi này sẽ được cấp vai trò cho mình, vai trò của người thứ $i$ sẽ là $a_i$ ($0\le a_i\le 1$, $a_i=0$ tức là vai trò của người đó là crewmate, $a_i=1$ tức là vai trò của người đó là imposustor). Imposustor sau khi nhận vai trò sẽ chọn 1 trong 2 người kề bên là crewmate và sát hại người đó. Hai imposustor không thể sát hại cùng 1 crewmate, imposustor này không thể sát hại imposustor kia.

huyhau6a2 định nghĩa một trò chơi được cho là gay cấn khi với mỗi imposustor, họ đều có thể tìm được 1 crewmate để sát hại. Ví dụ:

• Trò chơi 0 là trò chơi gay cấn vì không có imposustor
• Trò chơi 010 là trò chơi gay cấn vì người thứ hai là imposustor có thể chọn người thứ nhất hoặc thứ ba để sát hại
• Trò chơi 0110 là trò chơi gay cấn vì người thứ hai có thể chọn người thứ nhất và người thứ ba có thể chọn người thứ tư để sát hại
• Trò chơi 01110 không là trò chơi gay cấn vì người thứ ba không thể chọn được crewmate có thể sát hại
• Trò chơi 101 không là trò chơi gay cấn vì chỉ có 1 crewmate mà có tận 2 imposustor

huyhau6a2 đang thắc mắc với $n$ người thì sẽ có thể tạo ra bao nhiêu trò chơi gay cấn khác nhau. Hai trò chơi $a$ và $b$ được cho là khác nhau khi có tối thiểu một giá trị $i$ thỏa mãn $a_i\ne b_i$. Vì kết quả có thể rất lớn nên bạn hãy xuất kết quả sau khi $mod\ 998244353$

5
1
2
3
4
5

1
3
4
9
14