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]$$$。