Назовем целочисленный массив \(a_1, a_2, \dots, a_n\) хорошим, если \(a_i \neq i\) для всех \(i\).
Пусть \(F(a)\) — это количество пар \((i, j)\) (\(1 \le i < j \le n\)) таких, что \(a_i + a_j = i + j\).
Назовем массив \(a_1, a_2, \dots, a_n\) отличным если:
- \(a\) — хороший;
- \(l \le a_i \le r\) для всех \(i\);
- \(F(a)\) максимально возможное среди всех хороших массивов размера \(n\).
Для заданных \(n\), \(l\) и \(r\) посчитайте количество отличных массивов по модулю \(10^9 + 7\).
Выходные данные
Для каждого набора входных данных выведите количество отличных массивов по модулю \(10^9 + 7\).
Примечание
В первом наборе входных данных, можно показать, что максимальное \(F(a)\) среди всех хороших массивов \(a\) равно \(2\). Отличными являются следующие массивы:
- \([2, 1, 2]\);
- \([0, 3, 2]\);
- \([2, 3, 2]\);
- \([3, 0, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 0 3
4 -3 5
42 -33 55
69 -42 146
|
4
10
143922563
698570404
|