时间限制: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取余后的余数。
2 1 3
3
3 1 1
1
样例1,3个序列,[1,1,1],[2,2,2],[3,3,3];
样例2,1个序列,[1,1,1]。