题目背景

星港档案馆保存着许多星图目录。每份目录都是一个长度为 $n$ 的非降序编号表，编号范围在 $1$ 到 $m$ 之间。

档案馆的旧检索器使用固定的二分过程查询一个编号。你想知道：如果把所有可能的目录都拿来测试，并依次查询每个可能编号，检索器一共会进行多少次探测。

题目描述

给定一个非降数组 $a$、一个整数 $k$ 和区间 $[l,r]$，定义 $f(a,k,l,r)$ 为下面过程的返回值：

function f(a, k, l, r):
    if a 中不包含 k:
        return 0
    mid = floor((l + r) / 2)
    if a[mid] == k:
        return 1
    else if a[mid] < k:
        return 1 + f(a, k, mid + 1, r)
    else:
        return 1 + f(a, k, l, mid - 1)

对于给定的 $n,m$，称一个数组 $a$ 是合法的，当且仅当：

• $a$ 的长度为 $n$；
• $1\le a_1\le a_2\le \dots\le a_n\le m$。

你需要对所有合法数组 $a$，求

的总和，并对 $676767677$ 取模。

输入格式

第一行包含一个整数 $T$，表示测试用例数。

接下来 $T$ 行，每行包含两个整数 $n,m$。

输出格式

对每组测试数据，输出一行一个整数，表示答案对 $676767677$ 取模后的结果。

样例

输入

7
3 3
3 4
3 5
4 3
4 5
999967 99967
15 876543

输出

26
60
115
50
315
93903683
322710644

样例解释

在第一组测试数据中，一个合法数组是 $[2,2,3]$。此时：

• $f(a,1,1,n)=0$，因为 $1$ 不在数组中；
• $f(a,2,1,n)=1$，第一次探测的位置就是一个 $2$；
• $f(a,3,1,n)=2$，先探测到 $2$，再向右探测到 $3$。

因此这个数组的贡献为 $0+1+2=3$。对所有合法数组求和后得到 $26$。

数据范围

对于所有测试数据，满足：

• $1\le T\le 10^4$；
• $3\le n,m\le 10^6$；
• 所有测试用例的 $n$ 之和不超过 $10^6$；
• 所有测试用例的 $m$ 之和不超过 $10^6$；
• $676767677$ 是质数。

子任务