Bạn được cho số nguyên \(n\).

Yêu cầu: Hãy in ra số tập con khác nhau không lặp trong các số nguyên từ \(1\) đến \(n\).

Hai tập con được xem là khác nhau khi tồn tại một phần tử thuộc tập này nhưng không thuộc tập kia.

Input

• Chứa số nguyên \(n\) \((1 \leq n \le 10^9)\).

Output

• Chứa một số nguyên là đáp án của bài toán khi chia lấy dư cho \(10^9 + 7\).

Example

3

8

Các tập con là {}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}