题目背景

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

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

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

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

题目描述

我们定义『合法』序列，是长度为 $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$ 做出约束。