生产糖果

1s, 512MB

题目描述

你有一条自动化糖果生产线，现在你想要连续生产 $n$ 批糖果，每批糖果的产量有明确标准：必须在 $[l, r]$ 颗的区间范围内（即每批最少生产 $l$ 颗，最多生产 $r$ 颗）。

由于你的糖果工厂要向三家经销商供货，所以这 $n$ 批糖果的总产量必须是 $3$ 的整数倍。

请你合理分配这 $n$ 批糖果各自的产量，在满足上述所有要求的情况下，请问共有多少种不同的 “批次产量组合”？

由于答案较大，请你对 $10^9+7$ 取模。如果无论如何分配 $n$ 批糖果的产量，仍然无法满足要求，则输出 $0$。

输入格式

一行三个正整数 $n,l,r$

输出格式

一行一个整数，表示方案数模 $10^9+7$ 的结果

输入输出样例 #1

输入 #1

2 1 3

输出 #1

3

输入输出样例 #2

输入 #2

3 2 2

输出 #2

1

数据范围

对于 $10\%$ 的数据，有 $1\le n \le 5, 1\le l\le r\le 50$

对于 $30\%$ 的数据，有 $1\le n \le 17, 1\le l\le r\le 10^5$

对于 $100\%$ 的数据，有 $1\le n \le 2\times 10^6, 1\le l\le r\le 10^9$