$$$2^k$$$ 队参加季后赛。队伍的编号从 $$$1$$$ 到 $$$2^k$$$,按照实力递减的顺序排列。因此,$$$1$$$ 队是最强的,$$$2^k$$$ 队是最弱的。人数较少的球队总是会击败人数较多的球队。
首先,在称为种子的过程中,球队按某种顺序排列。每支球队都会被分配另一个从 $$$1$$$ 到 $$$2^k$$$ 的唯一值,称为种子,代表其在季后赛中的起始位置。
锦标赛由 $$$2^k - 1$$$ 场比赛组成。它们的举行方式如下:球队分成两对:种子队 $$$1$$$ 对阵种子队 $$$2$$$,种子队 $$$3$$$ 对阵种子队 $$$4$$$(完全按照这个顺序),依此类推(因此,$$$2^{k-1}$$$ 比赛在该阶段进行)。当一支球队输掉一场比赛时,该球队就会被淘汰。
之后,只剩下 $$$2^{k-1}$$$ 队。如果只剩下一支球队,则宣布该球队为冠军;否则,进行$$$2^{k-2}$$$游戏:在第一个游戏中,游戏“seed $$$1$$$ vs Seed $$$2$$$”游戏的获胜者与游戏“seed $$$3$$$ vs Seed $$$4$$$”的获胜者进行比赛,然后游戏“seed $$$5$$$ vs Seed $$$6$$$”游戏的获胜者与游戏“seed”的获胜者进行比赛$$$7$$$ 与种子 $$$8$$$",等等。重复此过程,直到只剩下一个团队。
比赛结束后,按照淘汰时的比赛阶段分配名额。特别是:
- 锦标赛获胜者获得 $$$1$$$ 名额;
- 决赛中被淘汰的队伍获得 $$$2$$$ 名次;
- 半决赛中被淘汰的两队均获得席位 $$$3$$$;
- 所有在四分之一决赛中被淘汰的球队都获得席位 $$$5$$$;
- 所有在 1/8 决赛中被淘汰的球队都获得 $$$9$$$ 名额,依此类推。
现在我们建立了规则,我们做了一些操纵。我们特别希望:
- $$$1$$$ 队伍(不是种子 $$$1$$$ 队伍)参加 $$$1$$$;
- 团队 $$$2$$$ 参加 $$$2$$$;
- $$$3$$$ 和 $$$4$$$ 队参加 $$$3$$$;
- 队伍从 $$$5$$$ 到 $$$8$$$ 参加 $$$5$$$,依此类推。
例如,这张图描述了锦标赛 $$$k = 3$$$ 的可能方式之一,以及球队的最终名次:
一些种子已经为一些球队保留了(显然,我们并不是唯一操纵锦标赛的球队)。我们必须用剩下的球队来填补剩下的种子,以达到预期的名次。有多少种方法可以做到这一点?由于该值可能很大,因此打印它对 $$$998\,244\,353$$$ 取模。
输入
第一行包含一个整数 $$$k$$$ ($$$0 \le k \le 19$$$) — 有 $$$2^k$$$ 队。
第二行包含 $$$2^k$$$ 整数 $$$a_1, a_2, \dots, a_{2^k}$$$ ($$$a_i = -1$$$ 或 $$$1 \le a_i \le 2^k$$$)。如果 $$$a_i \ne -1$$$,则团队 $$$a_i$$$ 拥有种子 $$$i$$$。否则,种子 $$$i$$$ 不会保留给任何球队。
所有不是 $$$-1$$$ 的值都是不同的。
输出
打印一个整数 - 填充非保留种子的方式数量,以便锦标赛按计划进行,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
2 1 2 3 4
输出 #1
0
输入 #2
2 1 3 4 2
输出 #2
1
输入 #3
1 -1 -1
输出 #3
2
输入#4
2 -1 -1 -1 -1
输出#4
16
输入 #5
3 -1 -1 -1 -1 2 -1 -1 -1
输出 #5
768
输入 #6
0 1
输出 #6
1