UOJ Logo

NOI.AC

1S 512MB

#122. 区间选择

统计

区间选择

输入m个区间,你希望从中选择尽量多的区间,使得两两不相交,也不能有公共端点。

假设输入的区间的$x_i$和$y_i$是1到n之间的整数,输入的区间不能有重复的。

输入的区间是没有顺序的(即输入[1,1] [2, 2] 和输入[2,2] [1, 1] 算作一种方案)

问有多少种选择这m个区间的方式,使得原问题的解,答案为l。

因为方案数很大,输出对$10007$取模的结果即可。

输入描述

一行三个整数$n, m, l$。

输出描述

输出一行一个整数,表示选择的方案数。

样例输入

3 3 1

样例输出

6

样例解释

[1, 1] [1, 2] [1, 3]
[2, 2] [1, 2] [2, 3]
[2, 2] [1, 2] [1, 3]
[2, 2] [2, 3] [1, 3]
[3, 3] [2, 3] [1, 3]
[2, 3] [1, 2] [1, 3]

对于以上六种输入,答案是1

样例输入

5 4 3

样例输出

246

数据规模与约定

对于100%的数据,满足$1 <= l <= n <= 50, 1 <= m <= min(50, n * (n + 1) / 2)$

对于30%的数据,满足$1 <= n <= 6$

对于70%的数据,满足$1 <= n <= 20$