#P10760. 澳洲袋鼠
澳洲袋鼠
题目描述
澳洲猴和澳洲袋鼠做一个游戏。第 只袋鼠的体积为 ,袋子的容量为 。袋鼠的袋子装入其他袋鼠后,这只袋鼠的体积仍为 。
一次操作可以把袋鼠 放入袋鼠 的袋子,条件如下。
- 袋鼠 目前没有装在其他袋鼠的袋子里。
- 袋鼠 的袋子目前为空。
- 。
澳洲猴会一直操作,直到无法进行任何一次操作。求可能的最终状态数量,对 取模。直接包含关系完全相同的两个状态视为同一种状态。
输入格式
第一行一个整数 。接下来 行,第 行包含两个整数 ,分别表示第 只袋鼠的体积和袋子容量。
输出格式
输出一行一个整数,表示最终状态总数对 取模后的结果。
5
4 3
3 1
6 5
2 1
4 2
4
样例说明
四种最终状态的直接包含关系如下, 表示袋鼠 在袋鼠 的袋子里。
- 。
- ,。
- ,。
- ,。
数据规模与约定
- 对于 的数据,。
- 对于 的数据,。
- 对于 的数据,,。
原附件末行将体积与袋子容量的不等式写反。上面的不等式与附件正文、样例和评测输入一致。