#P17949. GG
GG
给定三个整数 。从所有满足 的区间 中选出一些区间,也可以不选。
所选区间需要满足:
- 所有区间均包含在 内。
- 所有端点两两不同。若选了 个区间,则其 个左右端点必须互不相同。
- 可以从所选区间中找到 个区间 ,满足$$\ell_1<\ell_2<\cdots<\ell_a,\qquad r_a<r_{a-1}<\cdots<r_1.$$
- 可以从所选区间中找到 个区间 ,满足$$\ell_1<\ell_2<\cdots<\ell_b,\qquad r_1<r_2<\cdots<r_b.$$
后两条条件可以选择不同的区间集合;它们要求存在对应数量的区间,并不要求所选区间总数恰好为 或 。当数量为 时,该条条件自动满足。
求合法的区间集合数量,对 取模。
输入格式
一行三个整数 (,)。
输出格式
输出一行一个整数,表示合法方案数对 取模的结果。
样例 1
输入
2 0 0
输出
2
样例 2
输入
2 0 1
输出
1
样例 3
输入
5 1 2
输出
10
样例 4
输入
9 2 3
输出
504
样例 5
输入
100 14 22
输出
36993304