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 healthy và balance, 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,... , 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 \leq X_i \leq 2, ∀i ∈ {1, 2,..., n}.

Một dòng duy nhất chứa số nguyên n.

Kết quả bài toán sau khi chia lấy dư cho 1000000007.

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ả