← 返回题目列表

Codeforces · 1105/C

C. 阿尤布和丢失的阵列

中文机器翻译题面 查看原题

Ayoub 有一个大小为 $$$n$$$ 的整数数组 $$$a$$$ 并且这个数组有两个有趣的属性:

- 数组中的所有整数都在 $$$l$$$ 和 $$$r$$$ 之间(含)。
- 所有元素的总和可被 $$$3$$$ 整除。

不幸的是,Ayoub 丢失了他的数组,但他记得数组 $$$n$$$ 的大小以及数字 $$$l$$$ 和 $$$r$$$,所以他要求你找出恢复数组的方法数。

由于答案可能非常大,因此打印它以 $$$10^9 + 7$$$ 为模(即除以 $$$10^9 + 7$$$ 时的余数)。如果没有令人满意的数组(Ayoub 的内存有误),则打印 $$$0$$$。

输入

第一行也是唯一一行包含三个整数 $$$n$$$、$$$l$$$ 和 $$$r$$$ ($$$1 \le n \le 2 \cdot 10^5 , 1 \le l \le r \le 10^9$$$) - 丢失数组的大小和数组中数字的范围。

输出

打印除以 $$$10^9 + 7$$$ 恢复数组的方法数时的余数。

示例

输入 #1

2 1 3

输出 #1

3

输入 #2

3 2 2

输出 #2

1

输入 #3

9 9 99

输出 #3

711426616

注意

在第一个示例中,可能的数组为:$$$[1,2], [2,1], [3, 3]$$$。

在第二个示例中,唯一可能的数组是 $$$[2, 2, 2]$$$。