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}.
