Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 135

Solved: 19

Description
      X has a necklace with N pearls.He want to label each pearl with a lucky number a  (0=<L=<a<=R<10^9).Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7.To make it luckier,he make two rules.

 

Rule 1:any adjacent beads couldn’t have same lucky number.




an illegal situation


 

Rule 2:The repetitions that are produced by rotation around the center of the necklaceare all neglected.

 


They are the same.


      Now X will give you N, L, R, he wants you to help him calculate the number of different methods, because the number of method is so huge, so X just want you to tell him the remainder when divided by M.

      In this problem, M = 1,000,000,007.
Input
      The input consists of several test cases.(at most 1000)

      Every case has only two integers indicating N,L,R

      (0<=N<=10^9, 0<=L<=R<2^63)
Output
      For each case, you should output a single line indicates the remainder of number of different methods after divided by M.

sample input
3 3 55
3 5 125
3 8 1076
162 78923 987460
sample output
8
20
440
651834385
hint
source
Bo YANG
© 2015 HUST ACMICPC TEAM. All Right Reserved.