~Quốc~ đang chơi một trò chơi như sau:

Có ~1~ cầu thang có vô hạn bậc,bậc thấp nhất là ~0~,Quốc sẽ bắt đầu đi ở bậc số ~1~.Khi bắt đầu Quốc có ~1~ chỉ số gọi là ~jump~,ban đầu ~jump=0~.Khi ở một vị trí ~i~ bất kì,~Quốc~ có 2 thao tác và ~Quốc~ được thực hiện một trong hai:

• Đi xuống bậc số ~i - 1~ . Thao tác này không thể thực hiện liên tiếp hoặc trên cầu thang ~0~.

• Đi lên bậc số ~i~ ~+~ ~2^{jump}~.Sau thao tác này chỉ số ~jump~ sẽ tăng lên ~1~ đơn vị

Nhiệm vụ của ~Quốc~ như sau: Trò chơi sẽ đưa ra ~1~ số ~k~ bất kì,~Quốc~ phải đếm xem có bao nhiêu cách đến được bậc ~k~.

Lưu ý: ~Quốc~ có thể sẽ đến được bậc ~k~ và thực hiện một số thao tác để đến được bậc ~k~ lần nữa.

Input

Gồm ~1~ dòng chứa số nguyên dương ~k~ ~(0 \le k \le 10^9)~,

Output

In ra tổng số cách đến được bậc ~k~.

Sample Input 1

0

Sample Output 1

2

Sample Input 2

1

Sample Output 2

4

Giải thích

• Test 1:

Có ~2~ cách để đến bậc ~0~ là:

~Quốc~ bắt đầu từ bậc ~1~.

• Sử dụng thao tác loại ~1~, anh ấy đi xuống ~1~ bậc để đến bậc ~0~.

~Quốc~ bắt đầu từ bậc ~1~.

• Sử dụng thao tác loại ~1~, anh ấy đi xuống ~1~ bậc để đến bậc ~0~.
• Sử dụng thao tác loại ~2~, anh ấy đi lên bậc số ~0~ ~+~ ~2^0~ là bậc ~1~.
• Sử dụng thao tác loại ~1~, anh ấy đi xuống ~1~ bậc để đến bậc ~0~.

Test 2:

Có ~4~ cách để đến bậc ~1~ là:

~Quốc~ bắt đầu ở bậc ~1~. ~Quốc~ ở bậc ~1~.

~Quốc~ bắt đầu ở bậc ~1~.

• Sử dụng thao tác loại ~1~, anh ấy đi xuống ~1~ bậc để đến bậc ~0~.
• Sử dụng thao tác loại ~2~,anh ấy đi lên bậc số ~0~ ~+~ ~2^0~ là bậc ~1~.

~Quốc~ bắt đầu ở bậc ~1~

• Sử dụng thao tác loại ~2~, anh ấy đi lên bậc số ~1~ ~+~ ~2^0~ là bậc ~2~.
• Sử dụng thao tác loại ~1~, anh ấy đi xuống ~1~ bậc để đến bậc ~1~.

~Quốc~ bắt đầu ở bậc ~1~

• Sử dụng thao tác loại ~1~,anh ấy đi xuống ~1~ bậc để đến bậc ~0~.
• Sử dụng thao tác loại ~2~,anh ấy đi lên bậc số ~0~ ~+~ ~2^0~ là bậc ~1~.
• Sử dụng thao tác loại ~1~,anh ấy đi xuống ~1~ bậc để đến bậc ~0~.
• Sử dụng thao tác loại ~2~, anh ấy đi lên bậc số ~0~ ~+~ ~2^1~ là bậc ~2~.
• Sử dụng thao tác loại ~1~, anh ấy đi xuống ~1~ bậc để đến bậc ~1~.