🐇牛局长的圆形握手会-难
🔗 牛局长的圆形握手会
（兔猫信奥学院 · 牛局长 × 闪电 × 豹警官 × 朱迪 × 尼克）
故事背景
哨兵城安全局的 牛局长 携手助手 闪电 来到兔猫信奥学院参观，学院的明星学员 豹警官、朱迪 和 尼克 负责接待。为了活跃气氛，牛局长提议举行一场“圆形握手会”——
$num_people$ 名同学（人数保证为偶数）等距围成一个完美圆圈。 每位同学必须与除了自己的 恰好一位 同学握手，且最终总握手数为 。 当我们在圆上把每一对握手的两人用直线连起来时，所有连线都不能相交。
面对这样的规则，闪电写下一个问题：
“在满足上述条件的前提下，一共有多少种不相交握手方案？答案请对 $10^9+7$ 取模！”
豹警官已经摆好圆形队伍，朱迪和尼克各自拿着计数板等待你的答案……
题目描述
给定一个偶数 $num_people$，代表围成圆形的总人数。 所有人进行握手，要求：
- 每个人只与 一名 其他同学握手；
- 总握手数为 $num_people/2$；
- 任意两条表示握手的连线在圆内不得相交。
请计算满足条件的握手方案总数，对 $10^9+7$ 取模后输出。
输入格式
num_people
- $num_people$ —— 偶数，表示参加握手会的人数。
输出格式
ans
ans—— 满足条件的握手方案数 $\pmod{10^9+7}$。
样例
4
2
样例解释 1 四个人 (编号 $1,2,3,4$) 有两种合法握手方式：
- $$
- $$ 两条连线均不相交。
6
5
样例解释 2 当 $num_people=6$ 时，共有 $5$ 种不同的非相交握手方案（可自行画图验证）。
数据范围
| 参数 | 取值 |
|---|---|
| $2 \le num_people \le 1000$ | |
| $num_people \bmod 2 = 0$ |
提示
- 该计数问题等价于第 $\dfrac{num_people}{2}$ 个 卡特兰数。
- 建议使用动态规划或递推并结合取模运算来高效计算答案。
计数挑战，等你完成！ 🐮🤝🐆🐇🦊 —— 牛局长 & 兔猫信奥学院联合出题