Migrated from Lutece 3232 虾头卷狗莫得情感 · 其二

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

书接上回，得到了宝藏的诚哥历经千难万险归来后，趁某个夜黑风高无人知晓的时候在电脑前偷偷打开了学习资料，打算挑灯夜战独自开卷，从而理解成为并超越虾卷王。 然而，学习资料的压缩包解压需要密码。 众所周知，密码是可以通过字典攻击暴力破解的。在故事的背景中，密码的长度固定为 $L$ ，且密码的每一位都在 $[A , B]$ 范围内。同时为了提高信息在信道中传输时的抗干扰能力，密码的所有位和需要满足是 $4$ 的倍数。 现在诚哥想知道一共有多少种可能的密码，从而计算出暴力攻击需要的时间。

Input

第一行输入正整数 $L$ ——表示密码的长度。 第二行输入两个正整数 $A, B$ ——表示每一位的数值范围。

Output

输出一个正整数，表示密码的数量。 因为答案可能非常大，请输出答案对 $10^9+7$ 取模的结果。

Samples

2
1 3

3

1
7 47

10

Constraints

$1 \le L \le 10^6, 1\le A \le B \le 10^9$

Note

对于样例1，$[1, 3], [2, 2], [3, 1]$ 为可能的密码。 对于样例2，$[8], [12], [16], [20], [24], [28], [32], [36], [40], [44]$ 为可能的密码。

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming