Solution

考虑如何对 $S$ 计算 $g(S)$，一种计算方式是 $g(S)$ 等于满足 $S_{i-1}\neq S_i$ 的位置 $i$ 数量再加上 $1$。

先考虑那个 $+1$，一共有 $\binom{n+m}{n}$ 个 $\tt 01$ 串 $S$，这部分贡献为 $\binom{n+m}{n}$。

接着考虑对于位置 $i$，$S_i\neq S_{i-1}$ 的方案数。$S_{i-1}S_i$ 可能是 $\tt 01$ 或 $\tt 10$，然后其它 $\lvert S\rvert-2$ 的个位置随便排，这部分贡献为 $\binom{n+m-2}{n-2}\times 2$。可以发现对于所有 $i$ 贡献都一样，所以乘上 $n+m-1$。

因此答案为

$$\binom{n+m}{n}+(n+m-1)\times\binom{n+m-2}{n-2}\times 2 $$

// Problem: T561025 「FAOI-R5」Lovely 139
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T561025
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

namespace FastIO {
	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
	template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
	template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
}; using namespace FastIO;

using i32 = int32_t;
using u32 = uint32_t;
using u64 = uint64_t;
template <uint32_t MOD> struct mint {
	static constexpr u32 get_r() {
		u32 ret = MOD;
		for (i32 i = 0; i < 4; ++i) ret *= 2 - MOD * ret;
		return ret;
	}
	static constexpr u32 r = get_r();
	static constexpr u32 n2 = -u64(MOD) % MOD;
	static_assert(r * MOD == 1, "invalid, r * MOD != 1");
	static_assert(MOD < (1 << 30), "invalid, MOD >= 2 ^ 30");
	static_assert((MOD & 1) == 1, "invalid, MOD % 2 == 0");
	u32 a;
	constexpr mint() : a(0) {}
	constexpr mint(const int64_t &b) : a(reduce(u64(b % MOD + MOD) * n2)){};
	static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * MOD) >> 32; }
	constexpr mint &operator += (const mint &b) { if (i32(a += b.a - 2 * MOD) < 0) a += 2 * MOD; return *this; }
	constexpr mint &operator -= (const mint &b) { if (i32(a -= b.a) < 0) a += 2 * MOD; return *this; }
	constexpr mint &operator *= (const mint &b) { a = reduce(u64(a) * b.a); return *this; }
	constexpr mint &operator /= (const mint &b) { *this *= b.inverse(); return *this; }
	constexpr mint operator + (const mint &b) const { return mint(*this) += b; }
	constexpr mint operator - (const mint &b) const { return mint(*this) -= b; }
	constexpr mint operator * (const mint &b) const { return mint(*this) *= b; }
	constexpr mint operator / (const mint &b) const { return mint(*this) /= b; }
	constexpr bool operator == (const mint &b) const { return (a >= MOD ? a - MOD : a) == (b.a >= MOD ? b.a - MOD : b.a); }
	constexpr bool operator != (const mint &b) const { return (a >= MOD ? a - MOD : a) != (b.a >= MOD ? b.a - MOD : b.a); }
	constexpr mint operator-() const { return mint() - mint(*this); }
	constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul, n >>= 1; } return ret; }
	constexpr mint inverse() const { return pow(MOD - 2); }
	friend std::ostream &operator<< (std::ostream &os, const mint &b) { return os << b.get(); }
	friend std::istream &operator>> (std::istream &is, mint &b) { int64_t t; is >> t; b = mint<MOD>(t); return (is); }
	constexpr u32 get() const { u32 ret = reduce(a); return ret >= MOD ? ret - MOD : ret; }
	static constexpr u32 get_MOD() { return MOD; }
	explicit operator u32() const { return get(); }
}; using modint = mint<1000000007>;

#define MAXN 2000001
modint frac[MAXN], prac[MAXN];
void init(const int v = 2'000'000) {
	frac[0] = prac[0] = 1;
	for (int i = 1; i <= v; ++i) frac[i] = frac[i - 1] * modint(i);
	prac[v] = frac[v].inverse();
	for (int i = v - 1; i; --i) prac[i] = prac[i + 1] * modint(i + 1);
}
inline modint C(int x, int y) {
	return x < 0 || y < 0 || x < y ? modint(0) : frac[x] * prac[y] * prac[x - y];
}

void solve() {
	int n = read<int>(), m = read<int>();
	print<int>((modint((n + m - 1) * 2) * C(n + m - 2, n - 1) + C(n + m, n)).get(), '\n');
}

int main() { int t = read<int>(); init(); while (t--) solve(); return 0; }