题目背景
天地合一瞬,相爱永相随。
风云共缠绵,星月共辉辉。
情深如海渊,誓约山河坚。
此心与君共,天涯皆不远。
题目描述
我们定义『合法』序列,是长度为 n,且序列中的数都在 [1,V] 范围内的序列。
我们定义『天』序列,是『合法』的『单调不降』的序列。即对于『合法』序列 a 有 ∀i∈[2,n],ai−1≤ai。
我们定义『地』序列,是『合法』的『单调不升』的序列。即对于『合法』序列 b 有 ∀i∈[2,n],bi−1≥bi。
我们定义『天地合』是对于『天』序列 a 和『地』序列 b,有 ∀i∈[1,n],ai≤bi。
现在小 T 有 T 组询问,每组询问会给出你一个 n 和 V,求出有多少种『天地合』的方案。由于答案很大,请对 2009520301 取模。
20090520+20090301=?
输入格式
第一行包含一个整数 T,表示本测试点的测试数据个数。满足 1≤T≤105。
接下来有 T 组测试数据。
- 每组测试数据第一行是 2 个整数 n,V,满足 1≤n,V≤106。分别表示序列长度和元素值域。
输出格式
对于每组测试数据,输出『天地合』的方案个数对 2009520301 取模的结果。
提示
对于 40% 的数据,满足 1≤n,V≤10;
对于 60% 的数据,满足 1≤n,V≤103;
对于 100% 的数据,满足 1≤n,V≤106,1≤T≤105。
注意本题并没有对 ∑n 做出约束。