Đếm số không chứa chữ số 0

Đề bài

Cho một số nguyên dương \(n\).

Hãy đếm số lượng số nguyên dương có đúng \(n\) chữ số thỏa mãn đồng thời hai điều kiện:

• Số đó không chứa chữ số \(0\).
• Tổng các chữ số của số đó chia hết cho \(3\).

Vì kết quả có thể rất lớn, hãy in kết quả theo modulo \(1000000007\).

Input

Một dòng duy nhất chứa số nguyên dương \(n\).

Output

In ra một số nguyên duy nhất là số lượng số thỏa mãn yêu cầu.

Kết quả được lấy modulo \(1000000007\).

Ràng buộc

• Subtask 1 (20% số điểm): \(1 \le n \le 6\).
• Subtask 2 (30% số điểm): \(1 \le n \le 10^5\).
• Subtask 3 (50% số điểm): \(1 \le n \le 10^9\).

Ví dụ 1

Input:

1

Output:

3

Giải thích:

Các số có đúng \(1\) chữ số và không chứa chữ số \(0\) là:

1, 2, 3, 4, 5, 6, 7, 8, 9

Trong đó các số có tổng chữ số chia hết cho \(3\) là:

3, 6, 9

Vậy có \(3\) số thỏa mãn.

Ví dụ 2

Input:

2

Output:

27

Giải thích:

Các chữ số từ \(1\) đến \(9\) được chia thành ba nhóm:

• Nhóm dư \(0\) khi chia cho \(3\): \(3, 6, 9\).
• Nhóm dư \(1\) khi chia cho \(3\): \(1, 4, 7\).
• Nhóm dư \(2\) khi chia cho \(3\): \(2, 5, 8\).

Mỗi nhóm có đúng \(3\) chữ số.

Với số có \(2\) chữ số, ta cần tổng của hai chữ số chia hết cho \(3\).

Có ba trường hợp:

• Hai chữ số đều thuộc nhóm dư \(0\).
• Một chữ số thuộc nhóm dư \(1\) và một chữ số thuộc nhóm dư \(2\).
• Hai chữ số đều thuộc nhóm dư \(1\) hoặc đều thuộc nhóm dư \(2\).

Với mỗi chữ số đầu tiên, có đúng \(3\) cách chọn chữ số thứ hai để tổng chia hết cho \(3\).

Có \(9\) cách chọn chữ số đầu tiên nên có:

số thỏa mãn.