C. Аюб и утерянный массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Аюба был массив целых чисел $$$a$$$ длины $$$n$$$ и у этого массива было два необычных свойства:

  • Все целые числа в этом массиве были от $$$l$$$ до $$$r$$$ (включительно).
  • Сумма всех элементов в массиве делилась на $$$3$$$.

К сожалению, Аюб потерял свой массив, но он помнит размер массива $$$n$$$, а также числа $$$l$$$ и $$$r$$$, так что он попросил вас посчитать количество способов восстановить массив по этим данным.

Так как ответ может быть очень большим, выведите его по модулю $$$10^9 + 7$$$ (то есть остаток при делении на $$$10^9 + 7$$$). В случае если не существует ни одного подходящего массива (Аюб что-то перепутал) — выведите $$$0$$$.

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

Первая и единственная строка содержит три целых числа $$$n$$$, $$$l$$$ и $$$r$$$ ($$$1 \le n \le 2 \cdot 10^5 , 1 \le l \le r \le 10^9$$$) — размер массива и диапазон чисел в нём.

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

Выведите остаток при делении на $$$10^9 + 7$$$ количества способов восстановить массив.

Примеры
Входные данные
2 1 3
Выходные данные
3
Входные данные
3 2 2
Выходные данные
1
Входные данные
9 9 99
Выходные данные
711426616
Примечание

В первом примере возможны массивы $$$[1,2], [2,1], [3, 3]$$$.

Во втором примере единственный возможный массив — $$$[2, 2, 2]$$$.