数组重建

mac2025-02-27  6

数组重建

时间限制:1sec / 空间限制:256MB

题意

小明非常喜欢数字,有一天他在一本书上发现了一个包含 n n n个数字的数列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an,他对这个数列所展现出来的规律很感兴趣。

这个数列满足以下条件:

所有的数字的范围均在 [ l , r ] [l,r] [l,r]数列中所有的数字的和能被3整除

由于这本书被小刚借走了,但是小明又很想继续研究这个数列,所以他需要根据以上条件创造一个数列出来,现在请你帮助小明计算一下他能创造出多少个不同的数列,答案对1000000007取余。只要两个数列中某个相同位置的数字不同,那么这两个数列是不同的。

#输入

一行3个整数 n , l , r n,l,r n,l,r,含义如上所述,每两个整数之间用一个空格分格。

满足 1 < = n < = 1 0 5 , 0 < = l < = r < = 1 0 9 1 <= n <= 10^5,0 <= l <= r <= 10^9 1<=n<=105,0<=l<=r<=109

输出

一个整数,表示不同的数列的个数对1000000007取余后的余数。

样例1

输入

2 1 3

输出

3

样例2

输入

3 1 1

输出

1

Hint

样例1,3个序列,[1,1,1],[2,2,2],[3,3,3];

样例2,1个序列,[1,1,1]。

最新回复(0)