Тоглоом

Нийт $n$ ширхэг шоколад байна. $i$-р шоколад нь $w_i \times h_i$ хэмжээтэй бөгөөд Бат эсвэл Болдын аль нэгэнд харьяалагдана.

Тоглоомын явцад шоколадыг $90^\circ$-аар эргүүлэхийг хориглоно. Өөрөөр хэлбэл, $a \times b$ болон $b \times a$ хэмжээтэй шоколадуудыг өөр өөр гэж үзнэ.

Эдгээр шоколаднаас хоосон биш нэг дэд олонлогийг сонгож, үлдсэн шоколадуудыг хаяна. Дараа нь сонгосон шоколадуудыг ашиглан Бат, Болд хоёрын хооронд тоглоом эхэлнэ.

Тоглогчид ээлжээр нүүдэл хийнэ. Эхний нүүдлийг Бат хийнэ.

Батын ээлж ирэхэд дараах үйлдлүүдийн яг нэгийг хийнэ:

• Өөрийн нэг шоколадны бүх хэсгийг иднэ. Өөрөөр хэлбэл, $o_i = 0$ байх ямар нэг $i$-г сонгож, тухайн шоколадны бүх хэсгийг тоглоомоос хасна. Үүнд өмнө нь аль нэг тоглогчийн хуваасны үр дүнд үүссэн хэсгүүд ч багтана. Эдгээр хэсгийн нийт талбай нь $w_i \times h_i$-тэй тэнцүү байна.
• Аль ч шоколадны одоо байгаа нэг хэсгийг хуваана. Энэ нь заавал өөрийнх нь шоколад байх албагүй. Хуваах гэж буй хэсэг $a \times b$ хэмжээтэй бол түүнийг $x \times b$ болон $(a-x) \times b$ хэмжээтэй хоёр хэсэг болгон хувааж болно. Энд $x$ нь Фибоначчийн тоо бөгөөд $0 < x < a$ нөхцөлийг хангана.

Болдын ээлж ирэхэд дараах үйлдлүүдийн яг нэгийг хийнэ:

• Өөрийн нэг шоколадны бүх хэсгийг иднэ. Өөрөөр хэлбэл, $o_i = 1$ байх ямар нэг $i$-г сонгож, тухайн шоколадны бүх хэсгийг тоглоомоос хасна. Үүнд өмнө нь аль нэг тоглогчийн хуваасны үр дүнд үүссэн хэсгүүд ч багтана. Эдгээр хэсгийн нийт талбай нь $w_i \times h_i$-тэй тэнцүү байна.
• Аль ч шоколадны одоо байгаа нэг хэсгийг хуваана. Энэ нь заавал өөрийнх нь шоколад байх албагүй. Хуваах гэж буй хэсэг $a \times b$ хэмжээтэй бол түүнийг $a \times y$ болон $a \times (b-y)$ хэмжээтэй хоёр хэсэг болгон хувааж болно. Энд $y$ нь Фибоначчийн тоо бөгөөд $0 < y < b$ нөхцөлийг хангана.

Тоглогчийн ээлж ирэхэд хүчинтэй нүүдэл хийх боломжгүй бол тоглоом дуусна. Нүүдэл хийж чадахгүй болсон тоглогч хожигдоно.

Шоколаднуудын $2^n$ боломжит дэд олонлогоос сонголт хийнэ. Хэрэв ямар нэг $i \in \{1,\dots,n\}$ индексийн хувьд $i$-р шоколад нэг дэд олонлогт багтсан боловч нөгөө дэд олонлогт багтаагүй байвал эдгээр хоёр дэд олонлогийг ялгаатай гэж үзнэ.

Даалгавар: Хоёр тоглогч хоёулаа хамгийн оновчтой тоглоно гэж үзвэл Бат хожих боломжтой шоколаднуудын хоосон биш дэд олонлогуудын тоог олно уу. Хариуг $998244353$ тоонд модуль авсан утгаар хэвлэнэ.