#P18317. Easy Counting Problem
Easy Counting Problem
Easy Counting Problem
给定数组 ,你可以执行任意次以下操作,也可以一次不执行:
- 选择一个满足 且 的下标 ,删除数组的第 个元素。
- 删除后,数组变为 。这里 表示由 组成的子数组, 表示连接。空的部分直接忽略。
下标从1开始。每次操作判断的是当前数组的下标;删除后,后面的元素向前移动。
令 表示最优地执行这些操作后,数组能够达到的最小长度。
给定整数 ,考虑全部长度为 、满足 的数组,共有 个。求所有这些数组的 之和,对 取模。
输入格式
第一行包含整数 ,表示测试用例数。
接下来 行,每行包含两个整数 ,描述一组测试用例。
输出格式
对于每组测试用例,输出一行,包含所有符合条件的数组的 之和对 取模后的结果。
数据范围
- ;
- ;
- 。
样例
输入
9
2 2
2 1
3 1
3 2
3 3
3 5
6 3
23 10
900000000 900000000
输出
3
0
0
9
44
284
2534
243195864
193285282
说明
第一组测试中共有 个数组:
- :先删除第1个元素,再删除当前第1个元素,故 。
- :先删除第2个元素,再删除第1个元素,故 。
- :无法执行任何操作,故 。
- :删除第2个元素后剩下 ,故 。
因此答案为 。