题目描述

Ayoub 有一个长度为 $n$ 的整数数组 $a$，并且这个数组具有两个有趣的性质：

• 数组中的所有整数都在区间 $[l,r]$ 内；
• 数组所有元素之和能被 $3$ 整除。

不幸的是，Ayoub 把数组弄丢了，但他还记得数组长度 $n$ 以及数值范围 $l,r$，因此他想请你帮忙计算：有多少种不同的数组可以恢复出这样的性质。

由于答案可能非常大，请输出对 $10^9+7$ 取模后的结果。若不存在满足条件的数组，输出 $0$。

输入格式

输入仅一行，包含三个整数 $n,l,r$，分别表示丢失数组的长度以及数组元素的取值范围。

输出格式

输出一个整数，表示满足条件的数组个数对 $10^9+7$ 取模后的结果。

样例输入 1

2 1 3

样例输出 1

3

样例输入 2

3 2 2

样例输出 2

1

样例输入 3

9 9 99

样例输出 3

711426616

说明

样例解释

在第一个样例中，满足条件的数组有：

• $\texttt{[1,2]}$
• $\texttt{[2,1]}$
• $\texttt{[3,3]}$

在第二个样例中，唯一满足条件的数组是 $\texttt{[2,2,2]}$。

数据范围

对于 $20\%$ 的数据：

• $1\le n\le 20$
• $0\le r - l \le 10$

对于 $60\%$ 的数据：

• $1\le n\le 1000$
• $0\le r - l \le 1000$

对于 $100\%$ 的数据：

• $1\le n\le 2\cdot 10^5$
• $1\le l\le r\le 10^9$