Đất nước Văn Lang thời cổ xưa đã có những hiểu biết tân tiến về số học. Tương truyền rằng, vua Hùng Vương thứ 17 cùng các trưởng lão trong triều đình đã phát minh ra các số huyền bí. Các số này giúp chỉ dẫn đường vào kho tàng của đất nước. Theo các chứng tích khảo cổ, các nhà khoa học kết luận rằng số huyền bí cơ sở ~a~ bằng tích của ~(3^d - 1)~ với mọi ước số ~d > 0~ của ~a~.

Bờm thích số học đồng thời cũng rất thích tìm hiểu lịch sử đất nước. Bạn hãy giúp Bờm tính số huyền bí cơ sở ~a~ ~(1 \le a \le 10^{12})~. Do kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của số huyền bí cơ sở ~a~ khi chia cho ~20122007~.

Yêu cầu: Cho một số nguyên dương ~a~, hãy tìm số huyền bí cơ sở ~a~.

Dữ liệu

Vào từ file văn bản MYSTERY.INP một số nguyên dương ~a~.

Kết quả

Đưa ra file văn bản MYSTERY.OUT một số nguyên dương là phần dư của số huyền bí cơ sở ~a~ khi chia cho ~20122007~.

Ví dụ

MYSTERY.INP

10

MYSTERY.OUT

7291779

Giải thích: khi ~a = 10~ có các ước lớn hơn không là: 10, 5, 2, 1. Do đó số huyền bí cơ sở ~a~ được tính ~[(3^{10} - 1) \times (3^5 - 1) \times (3^2 - 1) \times (3^1 - 1)] = 228633856~ chia dư cho ~20122007~ được ~7291779~.

Giới hạn

• Subtask 1: 50% số test có ~a \le 10^9~;
• Subtask 2: 50% số test có ~a \le 10^{12}~.