Cho số tự nhiên ~n~, tìm số nguyên dương ~x~ nhỏ nhất sao cho ~2^n~ là ước của ~3^x - 1.~

Đầu vào

Số tự nhiên ~n~ ~(1 \le n \le 10^{18})~.

Đầu ra

Một số nguyên dương duy nhất là kết quả của bài toán trên, nếu không tồn tại số nào như vậy thì xuất ra ~0~.

Chú ý: Kết quả lấy mod không âm cho ~10^9 + 7~.

Ví dụ

Đầu vào:

1

Đầu ra:

1