#P1722. 矩阵 II

矩阵 II

题目背景

usqwedf 改编系列题。

题目描述

如果你在百忙之中抽空看题,请自动跳到第六行。

众所周知,在中国古代算筹中,红为正,黑为负……

给定一个 1×2n1\times 2n 的矩阵(usqwedf:这不是一个 2n2n 的队列么),现让你自由地放入红色算筹和黑色算筹,使矩阵平衡[即 i[1,2n]\forall i \in[1, 2n]1i1\sim i 格中红色算筹个数大于等于黑色算筹]。

问有多少种方案满足矩阵平衡(注意红色算筹和黑色算筹的数量必须相等)。

输入格式

正整数 nn

输出格式

方案数 tt100100 取模后的结果。

2
2

提示

样例解释:

  • 方案一:红,黑,红,黑

  • 方案二:红,红,黑,黑

数据范围:

1n1001\le n\le 100