Monsieur ~D-Tiramisu Wibu~ đã thành công phát hiện ra quy luật tăng trưởng của một loại tế bào ~X~. Mỗi tế bào ~X~ này có khả năng tạo ra hai tế bào ~X~ khác sau ~1~ đơn vị thời gian (kể từ lúc được tạo ra) trong suốt vòng đời của mình. Thành công này đã góp phần không nhỏ vào sự phát triển của nền y học thế giới.

Là một nghiên cứu sinh hỗ trợ ~D-Tiramisu Wibu~, bạn được giao nhiệm vụ tính xem từ ~1~ tế bào ~X~ ban đầu, sau ~n~ đơn vị thời gian sẽ thu được bao nhiêu tế bào. Biết trong ~n~ đơn vị thời gian, không có tế bào nào chết đi.

Vì con số này rất lớn nên bạn chỉ cần tìm phần dư của kết quả khi chia cho ~10^9+7~

Dữ liệu vào

Một dòng duy nhất chứa số ~n~ không âm.

Dữ liệu ra

Phần dư của số tế bào ~X~ sau ~n~ đơn vị thời gian khi chia cho ~10^9+7~.

Ví dụ

Dữ liệu vào

2

Dữ liệu ra

7

Giải thích

• Ban đầu có ~1~ tế bào X.
• Sau ~1~ đơn vị thời gian ~1~ tế bào tạo ra thêm ~2~ tế bào khác. Tổng cộng là ~3~ tế bào.
• Sau ~2~ đơn vị thời gian ~2~ tế bào tạo ra thêm ~4~ tế bào khác. Tổng cộng là ~7~ tế bào.

Giới hạn

• Có ~40\%~ trường hợp có ~n \le 29~.
• Có ~30\%~ trường hợp có ~n \le 10^6~.
• có ~30\%~ trường hợp có ~n \le 10^{18}~.