You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

天地合一瞬，相爱永相随。

风云共缠绵，星月共辉辉。

情深如海渊，誓约山河坚。

此心与君共，天涯皆不远。

题目描述

我们定义『合法』序列，是长度为 $n$，且序列中的数都在 $[1,V]$ 范围内的序列。

我们定义『天』序列，是『合法』的『单调不降』的序列。即对于『合法』序列 $a$ 有 $\forall i\in[2,n],a_{i-1}\leq a_i$。

我们定义『地』序列，是『合法』的『单调不升』的序列。即对于『合法』序列 $b$ 有 $\forall i\in[2,n],b_{i-1}\geq b_i$。

我们定义『天地合』是对于『天』序列 $a$ 和『地』序列 $b$，有 $\forall i\in [1,n],a_i\leq b_i$。

现在小 T 有 $T$ 组询问，每组询问会给出你一个 $n$ 和 $V$，求出有多少种『天地合』的方案。由于答案很大，请对 $2009520301$ 取模。

$20090520+20090301=\tt{?}$

输入格式

第一行包含一个整数 $T$，表示本测试点的测试数据个数。满足 $1\leq T \leq 10^5$。

接下来有 $T$ 组测试数据。

• 每组测试数据第一行是 $2$ 个整数 $n,V$，满足 $1\leq n,V\leq 10^6$。分别表示序列长度和元素值域。

输出格式

对于每组测试数据，输出『天地合』的方案个数对 $2009520301$ 取模的结果。

5
1 1
2 2
1 10
9 723
114514 191981

1
5
55
380188456
507522787

提示

对于 $40\%$ 的数据，满足 $1\leq n,V\leq 10$；

对于 $60\%$ 的数据，满足 $1\leq n,V\leq 10^3$；

对于 $100\%$ 的数据，满足 $1\leq n,V\leq 10^6$，$1\leq T\leq 10^5$。

注意本题并没有对 $\sum n$ 做出约束。