CF2211F.Learning Binary Search

You step into your first data structures class, where you are learning about binary search. You heard the professor yapping about why binary search works in $ O(\log{n}) $ . But you want to see if you can find a better bound.

Given a sorted array $ a $ of size $ n $ and an integer $ k $ , define $ f(a, k, l, r) $ as the result of the following code:

function f(a, k, l, r):<br></br>   if a does not contain k:<br></br>      return 0<br></br>   mid = floor((l+r) / 2)<br></br>   if a[mid]==k:<br></br>      return 1<br></br>   else if a[mid]<k:<br></br>      return 1+f(a, k, mid+1, r)<br></br>   else:<br></br>      return 1+f(a, k, l, mid-1)<br></br>

You are given two integers $ n $ and $ m $ . Define an array $ a $ good if:

• $ |a|=n $ (there are $ n $ elements in $ a $ ).
• $ 1 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq m $ (the array is nondecreasing, bounded by $ 1 $ below and bounded by $ m $ above).

You are interested in finding the sum of $ f(a,1,1,n)+f(a,2,1,n)+\ldots+f(a,m,1,n) $ over all good arrays $ a $ . Since this answer may be huge, output the answer modulo $ 676,767,677 $ . Note that $ 676,767,677 $ is a prime number.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains two integers $ n $ and $ m $ ( $ 3 \leq n,m \leq 10^6 $ ).

It is guaranteed that the sum of $ n $ does not exceed $ 10^6 $ over all test cases, and the sum of $ m $ does not exceed $ 10^6 $ over all test cases.

For each test case, output the requested sum modulo $ 676,767,677 $ on a new line.

In the first test case, one good array $ a $ is $ [2,2,3] $ . Here, $ f(a,1,1,n)=0 $ (as $ 1 $ is not present in $ a $ ), $ f(a,2,1,n)=1 $ , $ f(a,3,1,n)=2 $ . Therefore, the contribution of this good array is $ 0+1+2=3 $ .