JOI 君正在使用一个纵向 格、横向 格的矩形棋盘和若干棋子进行游戏。在游戏的初始状态下，至少有一个格子上放置了棋子，同时至少有一个格子上没有放置棋子。
该游戏的目标是：在尚未放置棋子的格子上逐个放置棋子，直到棋盘上所有格子都被放置棋子为止。但放置棋子需满足以下任一条件：
- 该格子正上方和正下方的格子上均已有棋子。
- 该格子左侧和右侧的格子上均已有棋子。
JOI 君从游戏的初始状态开始，对达成目标所需的放置顺序总数感到好奇。然而，这个数值可能非常巨大。
你的任务是：代替 JOI 君，求出从游戏初始状态开始到达成目标为止，所有可能的棋子放置顺序的数量，并对 取模。
:::
:::