У Аюба был массив целых чисел \(a\) длины \(n\) и у этого массива было два необычных свойства:
- Все целые числа в этом массиве были от \(l\) до \(r\) (включительно).
- Сумма всех элементов в массиве делилась на \(3\).
К сожалению, Аюб потерял свой массив, но он помнит размер массива \(n\), а также числа \(l\) и \(r\), так что он попросил вас посчитать количество способов восстановить массив по этим данным.
Так как ответ может быть очень большим, выведите его по модулю \(10^9 + 7\) (то есть остаток при делении на \(10^9 + 7\)). В случае если не существует ни одного подходящего массива (Аюб что-то перепутал) — выведите \(0\).
Выходные данные
Выведите остаток при делении на \(10^9 + 7\) количества способов восстановить массив.
Примечание
В первом примере возможны массивы \([1,2], [2,1], [3, 3]\).
Во втором примере единственный возможный массив — \([2, 2, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1 3
|
3
|
|
2
|
3 2 2
|
1
|
|
3
|
9 9 99
|
711426616
|