F. Изучение бинарного поиска
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы пришли на своё первое занятие по алгоритмам, где изучаете бинарный поиск. Вы слышали, как преподаватель рассуждал о том, почему бинарный поиск работает за $$$O(\log{n})$$$. Но вам хочется понять, нельзя ли получить лучшую оценку.

Дан отсортированный массив $$$a$$$ размера $$$n$$$ и целое число $$$k$$$. Определим $$$f(a, k, l, r)$$$ как результат выполнения следующего кода: 

функция f(a, k, l, r):
   если a не содержит k:
      вернуть 0
   mid = floor((l+r) / 2)
   если a[mid]==k:
      вернуть 1
   иначе, если a[mid]<k:
      вернуть 1+f(a, k, mid+1, r)
   иначе:
      вернуть 1+f(a, k, l, mid-1)

Вам даны два целых числа $$$n$$$ и $$$m$$$. Назовём массив $$$a$$$ хорошим, если:

  • $$$|a|=n$$$ (в массиве $$$a$$$ ровно $$$n$$$ элементов).
  • $$$1 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq m$$$ (массив неубывающий, все его элементы не меньше $$$1$$$ и не больше $$$m$$$).
Вам нужно найти сумму $$$f(a,1,1,n)+f(a,2,1,n)+\ldots+f(a,m,1,n)$$$ по всем хорошим массивам $$$a$$$. Так как ответ может быть очень большим, выведите его по модулю $$$676\,767\,677$$$. Обратите внимание, что $$$676\,767\,677$$$ — простое число.
Входные данные

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \leq n,m \leq 10^6$$$).

Гарантируется, что сумма всех $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$, и сумма всех $$$m$$$ по всем наборам входных данных также не превосходит $$$10^6$$$.

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

Для каждого набора входных данных выведите на отдельной строке требуемую сумму по модулю $$$676\,767\,677$$$.

Пример
Входные данные
7
3 3
3 4
3 5
4 3
4 5
999967 99967
15 876543
Выходные данные
26
60
115
50
315
93903683
322710644
Примечание

В первом наборе входных данных одним из хороших массивов $$$a$$$ является $$$[2,2,3]$$$. Здесь $$$f(a,1,1,n)=0$$$ (так как $$$1$$$ отсутствует в $$$a$$$), $$$f(a,2,1,n)=1$$$, $$$f(a,3,1,n)=2$$$. Следовательно, вклад этого хорошего массива равен $$$0+1+2=3$$$.