#P18739. [正睿NOI2021训练] 第一题

[正睿NOI2021训练] 第一题

第一题

在一个 2×n2\times n 的网格中选择若干格子涂黑,满足:

  1. 所有黑格四连通。
  2. 不存在四个黑格组成 2×22\times2 的正方形。
  3. 不存在四个黑格组成 T 字形,即一个黑格及其三个上下左右相邻格子不能同时为黑色。

已知第一行恰有 aa 个黑格,第二行恰有 bb 个黑格。求不同涂色方案数,对 998244353998244353 取模。网格的位置固定,旋转或反射后的不同格子集合仍是不同方案。

输入格式

一行三个整数 n,a,bn,a,b。

输出格式

一个整数,表示方案数模 998244353998244353 的结果。

数据范围

3≤n≤5×1063\le n\le5\times10^6,0≤a,b≤n0\le a,b\le n,a+b≥1a+b\ge1。允许其中一行没有黑格。

样例 1

输入

5 2 4

输出

4

样例 2

输入

3 0 1

输出

3

第二个样例中,只有第二行的一个格子涂黑,共有三个可选位置。