luogu#P7698. [COCI2009-2010#4] KABOOM

[COCI2009-2010#4] KABOOM

题目背景

请注意本题特殊的时间限制。

Luka 在化学实验室发现了一条有趣的胶带。

题目描述

胶带被分成 nn 个等长的段,很容易在两端之间弯曲,但最多只能够弯曲 180180 度。胶带的一面完全覆盖着一种极易挥发的化学物质。如果化学物质与本身接触,它将会爆炸。胶带的另一面不一定完全覆盖住,只有前 AA 段和后 BB 段被覆盖了完全相同的化学物质。

编写一个程序,计算 Luka 弯曲胶带的不同方案数。如果两个方案有至少一段的弯曲情况不同,那么这两个方案算作不同的方案。

这个答案可能很大,你只需要输出答案1030110301 的结果

输入格式

输出仅一行,三个正整数 n,A,Bn,A,B,分别表示胶带的段数,没有完全覆盖的那一面从左边开始被覆盖的段数和从右边开始被覆盖的段数。

输出格式

输出仅一行,表示 Luka 弯曲胶带的不同方案数模 1030110301 的值。

4 1 1
6
5 2 2
1
6 1 2
7

提示

【样例 1 解释】

下图给出了样例 1 对应的所有的弯曲方案。请注意,为了能够清晰地观察胶带的弯折情况,图中的胶带仅弯折了 9090,实际上 Luka 会将这几段胶带弯折 180180 度。

【数据范围】

对于所有数据,0<n,A,B10000<n,A,B \leqslant 1000 且满足 A+BnA+B\leqslant n

【题目来源】

本题来源自 COCI 2009-2010 CONTEST 4 T5 KABOOM,按照原题数据配置,满分 120120 分。

Eason_AC 翻译整理提供。