Несколько людей стоит в ряд. Некоторые из них уходят из строя. Если быть более точным, то каждую секунду происходит следующее.

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

Процесс продолжается k секунд.

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

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

Первая строка содержит количество тестов T (1 ≤ T ≤ 105).

Каждая из следующих T строк содержит целые числа n, l, r и k (1 ≤ n, l, r, k ≤ 1018). Гарантируется, что k ≤ n - min(l, r) + 1, то есть в каждую из k секунд как минимум один из вариантов в шаге 2 возможен.

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

Вывести T строк: i-ая строка содержит ответ к i-му тесту по модулю 109 + 7.