Lần này bài tập bạn được giao là: hãy tính số lượng dãy bit có độ dài là ~n~.

Ví dụ: nếu ~n=3~, thì câu trả lời đúng lẽ là 8, vì các dãy bit thoả mãn là ~000, 001, 010, 011, 100, 101, 110, 111~

Input

• Chỉ một dòng duy nhất chứa số nguyên ~n~.

Output

• In kết quả chia lấy dư cho ~10^9 + 7~

Constraints

~1 ≤ n ≤ 10^6~

Example

Input

3

Ooutput

8

Cho dãy a gồm n số nguyên dương. Hãy cho biết có bao nhiêu cặp số trong dãy có tổng chia hết cho 3. Nói cách khác, bạn phải đếm xem có bao nhiêu cặp chỉ số ~i, j~ (~1 ≤ i < j ≤ n~) sao cho tổng ~a_i + a_j~ chia hết cho 3.

Dữ liệu vào:

· Dòng 1: Một số nguyên duy nhất ~n~ (~1 ≤ n ≤ 5.10^6~).

· Dòng 2: Ghi n số nguyên dương ~a_1,a_2,...,a_n~(~1 ≤ a_i ≤ 10^{18}~) là các phần tử của dãy.

Kết quả:

· Một dòng duy nhất ghi số lượng cặp số của dãy ~a~ có tổng chia hết cho ~3~.

Ví dụ:

Input1

5
3 4 2 3 4

Output1

3

Input2

4
3 6 9 12

Output2

6

abcnickname là một cậu học sinh rất có duyên với số 8, cậu có 8 người bạn gái, 8 năm học sinh giỏi, 8 cái máy tính, điểm thi HSG cũng không lên nỗi con số 9..... Bởi vậy từ lâu cậu đã coi số 8 là con số may mắn của đời mình.

Hôm nay trên lớp abcnickname được 1 trong 8 bạn gái của mình giảng bài về ước của các số, vậy nên abcnickname cũng đã nghĩ về một vấn đề toán học liên quan đến con số 8 của cuộc đời mình. Cậu tự hỏi nếu có 1 dãy số tự nhiên từ ~l~ đến ~r~ thì trong dãy đó có bao nhiêu số tự nhiên có đúng 8 ước nguyên dương. abcnickname vì suy nghĩ bài toán này liên tiếp 8 ngày 8 đêm đến mất ăn mất ngủ mà vẫn chưa xong. Vì vậy các bạn hãy giúp cậu ấy nhé, nếu làm được thì sẽ được abcnickname tặng một món quà đấy !

Input

• Dòng đầu tiên là số truy vấn ~Q~.
• ~Q~ dòng tiếp theo mỗi dòng là hai số nguyên dương ~l~ và ~r~.

Output

• ~Q~ dòng là kết quả của các truy vấn tương ứng.

Scoring

Subtask1 (30% số điểm): ~Q ≤ 10~ và ~l,r≤10^5~.

Subtask2 (30% số điểm): ~Q ≤ 100~ và ~l,r≤10^7~.

Subtask3 (40% số điểm): ~Q ≤ 10^5~ và ~,r ≤ 10^7~.

Example

Input

1
128 129

Output

1