Черга

Кілька людей стоять у ряд. Деякі з них покидають свої позиції. Щосекунди відбувається наступне:

1. Люди, що залишилися, перенумеровуються зліва направо від 1 до m, де m — кількість людей у ряді.

2. Одна людина покидає ряд. Це може бути людина з номером l або з номером m - r + 1, де l і r — певні константи. Один з варіантів може бути неможливим, якщо l > m або r > m. Проте обмеження гарантують, що хоча б один з варіантів завжди можливий.

Процес триває k секунд.

Вам задано числа n, l, r і k. Потрібно визначити, яка різна множина людей може залишитися після k секунд. Дві множини людей вважаються різними, якщо існує людина, яка присутня в одній множині і відсутня в іншій. Оскільки відповідь може бути великою, виведіть її за модулем 10^9 + 7.

Вхідні дані

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

Кожен з наступних T рядків містить цілі числа n, l, r і k (1 ≤ n, l, r, k ≤ 10^18). Гарантується, що k ≤ n - min(l, r) + 1, тобто в кожну з k секунд принаймні один з варіантів у кроці 2 можливий.

Вихідні дані

Виведіть T рядків: i-ий рядок містить відповідь для i-го тесту за модулем 10^9 + 7.

Приклади