Назовем целочисленный массив \(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\).
Примечание
В первом наборе входных данных, можно показать, что максимальное \(F(a)\) среди всех хороших массивов \(a\) равно \(2\). Отличными являются следующие массивы:
- \([2, 1, 2]\);
- \([0, 3, 2]\);
- \([2, 3, 2]\);
- \([3, 0, 1]\).