F. Хамед и АгаБалаСар
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хамид написал $$$3014$$$ строк кода для задачи a+b и отдал из них $$$10$$$ строк Хамеду; после этого Хамед придумал следующую задачу.

Даны два целых числа $$$n$$$ и $$$m$$$.

Массив $$$a_1,a_2,\ldots,a_n$$$ называется высоким, если и только если выполняются все следующие условия:

  • Все элементы в $$$a$$$ — целые числа от $$$0$$$ до $$$m$$$;
  • $$$a_1 + a_2 + \cdots + a_n = m$$$;
  • $$$a_n=\max\left([a_1, a_2, \ldots, a_n]\right)$$$.

Определим $$$f(a)$$$ как в следующем псевдокоде:

function f(array a):
    pos := 1
    res := 0
    определим nxt[x] как массив, где nxt[x] является наименьшим индексом y таким, что
                                    y > x и a[y] > a[x],
                              и не определено, если такого y нет
    while pos < n:
        if a[pos] < a[n]:
            res += a[nxt[pos]] - a[pos]
            pos := nxt[pos]
        else:
            pos += 1
    return res

Найдите сумму $$$f(a)$$$ по всем высоким массивам $$$a_1,a_2,\ldots,a_n$$$, по модулю $$$10^9+7$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$) — длина высокого массива и сумма всех элементов в высоком массиве.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — сумму $$$f(a)$$$ по всем высоким массивам $$$a_1,a_2,\ldots,a_n$$$, по модулю $$$10^9+7$$$.

Пример
Входные данные
8
2 5
3 4
4 6
5 10
6 23
100 100
142857 33333
200000 0
Выходные данные
9
14
76
985
142112
771227753
865580631
0
Примечание

В первом наборе входных данных есть три высоких массива:

  • $$$f([0, 5]) = 5$$$;
  • $$$f([1, 4]) = 3$$$;
  • $$$f([2, 3]) = 1$$$.

Таким образом, ответ равен $$$5+3+1=9$$$.

Во втором наборе входных данных есть шесть высоких массивов:

  • $$$f([0, 0, 4]) = 4$$$;
  • $$$f([0, 1, 3]) = 3$$$;
  • $$$f([1, 0, 3]) = 2$$$;
  • $$$f([1, 1, 2]) = 1$$$;
  • $$$f([0, 2, 2]) = 2$$$;
  • $$$f([2, 0, 2]) = 2$$$.

Таким образом, ответ равен $$$4+3+2+1+2+2=14$$$.

В пятом наборе входных данных возможен такой высокий массив:

  • $$$f([3, 1, 4, 1, 5, 9]) = 6$$$.