Học tập và sinh sống tại một trường gần biển, ~J~ đã rèn luyện được cho mình một thú vui tao nhã: thưởng thức hải sản. 3 món khoái khẩu của ~J~ có thể kể đến là: sò lông nướng mỡ hành, sò huyết hấp sả, ốc len xào dừa (tạm đánh số 3 món ăn này lần lượt là 0, 1, 2 cho ngắn gọn). Mỗi ngày, ~J~ đều đến bờ biển để ăn một trong ba món khoái khẩu của mình để được tận hưởng sở thích và lấy lại tinh thần của mình sau một ngày học tập mệt mỏi. Tuy nhiên, là một sinh viên sống lành mạnh và cân bằng, ~J~ muốn thực đơn của mình trong ~N~ ngày phải đa dạng và đầy đủ chất dinh dưỡng. Bằng kiến thức của mình, ~J~ biết được rằng nếu tổng của số hiệu các món ăn trong ~N~ ngày là một bội số của 3 thì chuỗi bữa ăn này là một chuỗi ngày hợp lí về mặt dinh dưỡng. Vậy thì ~J~ tò mò muốn biết có tổng cộng bao nhiêu cách khác nhau để sắp xếp một chuỗi ngày ăn uống chất lượng.

Nói một cách ngắn gọn, bạn hãy đếm số dãy số nguyên ~X = (X_1, X_2, \ldots, X_n)~ gồm ~n~ phần tử thỏa mãn:

• Tổng các phần tử của ~X~ chia hết cho ~3~.

• ~0 \le X_i \le 2~ với mọi ~1 \le i \le n~.

Dữ liệu

Một dòng duy nhất chứa số nguyên dương ~n~ ~(n \le 10^{18})~.

Kết quả

In ra kết quả bài toán sau khi chia lấy dư cho ~10^9 + 7~.

Ví dụ

Sample Input

2

Sample Output

3

Giải thích ví dụ

Với ~n = 2~ ta có các dãy ~X~ sau:

• ~X = (1, 2)~ tức là ngày thứ nhất ăn sò huyết hấp sả, ngày thứ hai ăn ốc len xào dừa

• ~X = (0, 0)~ tức là cả hai ngày đều ăn sò lông nướng mỡ hành

• ~X = (2, 1)~ tức là ngày thứ nhất ăn ốc len xào dừa, ngày thứ hai ăn sò huyết hấp sả

Chấm điểm

• Subtask ~1~ ~(40\%)~: ~1 \le n \le 10~

• Subtask ~2~ ~(32\%)~: ~10 < n \le 10^3~

• Subtask ~3~ ~(28\%)~: ~10^3 < n \le 10^{18}~