Для цілого числа \(K\) і перестановки \(A=[A_1,A_2,…,A_N]\) значень від 1 до \(N\) ми визначаємо функцію \(f(A)\), яка повертає кількість пар цілих чисел (\(i,j\)) таких, що

• \(1 \le i < j \le N\)

• \(j>i + K\)

• \(A_j > A_i\)

• Для всіх \(x \geq (i+1)\) і \(x \le (j-1)\), \(A_x < A_i\)

• для всіх \(x < i\), \(A_x < A_i\)

Простіше кажучи, у підмасиві \(A[1..j]\), \(A_i\) -- другий за величиною елемент, а \(A_j\) -- найбільший елемент.

Задається \(K\). Обчисліть \(\sum(f(A))\) для ВСІХ перестановок \(A\) розміру \(N\).

Оскільки відповідь може бути дуже великою, знайдіть суму за модулем \(10^9 + 7\).

Формат вхідних даних

Перший рядок містить ціле число \(T\) (\(1 \le T \le 10^5\)) - кількість тестів.

Потім слідують \(T\) рядків, кожен рядок містить цілі числа \(N, K\) (\(1 \le K < N \le 10^7\)).

Формат вихідних даних

Для кожного тесту в окремому рядку виведіть шукану суму.

Примітка

Тест 1

• \(f(A) = 0\) для перестановок {1,2,3}, {1,3,2}, {2,3,1}, {3,1,2}, {3,2,1}.

• \(f(A) = 1\) для перестановки {2,1,3}.

Приклад вхідних даних

3
3 1
4 2
5 3

Приклад вихідних даних

1
2
6