An có một mảng gồm ~ n ~ phần tử. Nhưng anh ta lại không nhớ chính xác mảng gồm những phần tử nào. Anh ta chỉ nhớ mảng có 2 đặc điểm sau:

• Mỗi phần tử trong mảng đều thuộc ~ [l,r] ~ .
• Tổng các phần tử của mảng chia hết cho 3.

Hãy giúp An đếm xem có tất cả bao nhiêu dãy thỏa mãn điều kiện trên( với ~ n , l ,r ~ được nhập từ đầu vào ). Vì kết quả rất lớn nên chỉ cần in số dư của nó cho ~10^9 +7 ~

Input

3 số ~ n, l, r  ~ trên cùng 1 dòng ( ~ 1\le n \le 10^6 ~, ~ 1\le l \le r \le 10^9 ~ ).

Output

In ra kết quả theo yêu cầu bài toán

Sample

Input #1

2 1 3

Output #1

3

Hint

Trong ví dụ trên có 3 dãy có thể đó là: ~ (1,2) ~ , ~ (2,1) ~ , ~ (3,3) ~.