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 vờ 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 sau một ngày học tập mệt mỏi. Tuy nhiên là một sinh viên sống healthy và balance, J muốn 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 nguyên ~ X = (X_1, X_2, …, 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 ≤ X_i ≤ 2 ~ ~ ∀i ∈ {1,2,…,n} ~

Dữ liệu vào

• Ghi số nguyên dương ~ n ~

Kết quả

Một số nguyên duy nhất là kết quả bài toán chia lấy dư cho ~ 10^9+7 ~

Ràng buộc

• subtask 1 (40%): ~ 1 ≤ n ≤ 10 ~
• subtask 2 (32%): ~ 10 < n ≤ 10^3 ~
• subtask 3 (28%): ~ 10^3 < n ≤ 10^{18} ~

Ví dụ:

Input 1

2 

Output 1

3