#P1041. 质检序列规划
质检序列规划
题目描述
某智能化工厂的质检流水线上有 个按顺序排列的检测点。为了测试质检设备的稳定性和极限响应,工程师需要人工设计一组包含 个元素的检测指标序列。为了符合测试标准,这组序列必须严格满足以下要求:
- 该序列总共包含 个检测指标数据;
- 每个数据点的指标必须是 到 之间的正整数;
- 整个指标序列中,恰好有且仅有一对数据点的指标是完全相同的;
- 整个指标序列必须呈现出“先增后降”的单峰形态。也就是说,存在一个特定的“顶峰”位置 ,使得在第 个数据点之前,指标序列严格单调递增;在第 个数据点之后,指标序列严格单调递减(形式化地说,若指标序列为 ,则当 时满足 ,当 时满足 )。
现在,工程师想知道,一共有多少种不同的检测指标序列能够同时满足上述所有条件?
由于符合条件的方案数可能非常庞大,你只需要输出最终的方案数对 取模后的结果。
输入格式
第一行包含两个正整数 和 (),分别表示流水线上的检测点数量以及指标的最大可能边界值。
输出格式
输出一个整数,表示满足上述所有条件的不同指标序列的总数量,答案对 取模。
样例 1
3 4
6
样例 2
3 5
10
样例 3
42 1337
806066790
样例 4
100000 200000
707899035
样例说明
第一个样例中的数组有:
- ;
- ;
- ;
- ;
- ;
- 。
数据范围
- 对于 的数据,。
- 对于另外 的数据,。
- 对于 的数据,。