Chắc hẳn các bạn học sinh chúng ta ai cũng biết bài toán cổ về bàn cờ vua và hạt thóc. Và hôm nay các bạn sẽ được làm quen với một biến thể của nó: Cho một dãy ô vuông được đánh thứ tự từ trái qua phải. Ô vuông thứ nhất chứa 1 hạt thóc, các ô vuông tiếp theo mỗi ô vuông chứa số hạt thóc gấp đôi ô vuông đứng liền kề trước nó. Ta chọn một ô vuông thứ a bất kỳ trên dãy (a>0).

Yêu cầu: Tính xem tổng số hạt thóc trong các ô vuông từ 1 đến a chia cho 127 sẽ dư bao nhiêu trong thời gian nhanh nhất  có thể.

Dữ liệu vào: Gồm một dòng duy nhất là số nguyên a (a ≤ 10¹⁸).

Dữ liệu ra: Là một số nguyên duy nhất thỏa mãn yêu cầu bài.