Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Tèo nuôi ~N~ con chuồn chuồn, vì tinh nghịch nên Tèo dán lên mỗi con chuồn chuồn một số ~X (1 \le X \le 3)~. Sau khi dán xong, Tèo bỗng nhiên nãy ra một câu hỏi: "Có bao nhiêu cách dán các số lên các con chuồn chuồn sao cho tổng các số sau khi dán chia hết cho 3 ?".

Vì có quá nhiều con chuồn chuồn nên Tèo nhờ bạn giúp. Bạn hãy giúp Tèo giải câu hỏi trên nhé.

Dữ liệu

  • Gồm một dòng duy nhất chứa số nguyên ~N (1 \le N \le 10^{18})~.

Kết quả

  • Gồm một số nguyên duy nhất là kết quả bài toán (Kết quả lấy phần dư cho ~10^9 + 7~).

Sample Input

2

Sample Output

3

Giải thích

  • Các cách đánh số các con chuồn chuồn là: ~(1, 2), (2, 1), (3, 3)~.

Comments

Please read the guidelines before commenting.



  • 0
    anle82917  commented on May 24, 2024, 1:11 p.m.

    Bài này giải toán.