Sau khi bị letangphuquy bắt xếp tháp trong \(X > 10^9 + 7\) phút liên tục, bé a520anhlnb đã xếp được tháp độ cao \(3^n\) trong truyền thuyết (gồm \(3^n\) khối xếp chồng lên nhau). Mỗi khối có thể được tô bởi một trong ba màu : đỏ, lam, lục. Quý tò mò liệu có thể có bao nhiêu cách tô màu khác nhau? Hai cách tô màu được xem là khác nhau nếu tồn tại một khối có màu khác trong mỗi cách. Nhưng do quá mải mê luyện code tham lam để leo rank xám CF nên Quý đã quên cách làm bài này. Anh ấy cần sự trợ giúp của bạn. Vì số lượng rất lớn nên các bạn hãy đưa ra kết quả theo modulo \(10^9 + 7\) nhé.

Input

• Dòng đầu chứa một số nguyên dương \(n (1 \le n \le 10^9)\)

Output

• Một dòng duy nhất chứa số lượng cách tô, chia lấy dư cho \((10^9 + 7)\)

Example

1

27