[Bài 5 trong chuỗi bài Mỗi tuần một bài toán 2025]

Các coder có thể xem thông tin thêm tại đây: Thông tin về contest

Xét phép biến đổi ~f~ tác động lên một xâu nhị phân: biến mỗi số ~0, 1~ trong đó thành ~1~, ~01~ cùng lúc. Xuất phát từ ~1~ (coi như ~s_1~), ký hiệu ~s_n~ là xâu sinh ra được sau khi tác động ~f~ lên xâu gốc tất cả ~n~ lần. Cụ thể là

~1 \to 01 \to 101 \to 01101 \to ...~

Chưa dừng lại ở đó, người ta còn ghép các xâu ~s_1, s_2, ...,s_n~ lại với nhau, tạo thành xâu ~t_n.~ Như vậy xâu ~t_4~ sẽ là ~10110101101~ tạo thành từ việc ghép 4 xâu đầu tiên trong dãy ~s_n~ ở trên.

Cho trước số nguyên dương ~n~, câu hỏi đặt ra là:

1) Có bao nhiêu số ~0~ trong xâu ~t_n~?

2) Trong các xâu ~t~ thì số ~0~ thứ ~n~ nằm ở vị trí bao nhiêu?

Input

Số nguyên dương ~n~ duy nhất với ~1 \le n \le 10^{10}~.

Output

Câu trả lời cho hai câu hỏi trên, kết quả có thể ra lớn nên lấy dư khi chia cho ~10^9+7.~

Sample input 1

1

Sample output 1

0 2

Sample input 2

4

Sample output 2

4 10