Lipon là một cậu bé đam mê toán học, cậu rất muốn khám phá ra nhưng điều mới lạ trong toán học. Một ngày nọ, cậu biết đến dãy số Fibonacci. Lipon tìm hiểu sâu hơn thì biết được dãy số ấy được tạo ra bởi Leonardo Fibonacci. Cậu ấy liền nghĩ ra một dãy số và đặt tên nó là dãy số Lipon.

Dãy số Lipon được định nghĩa như sau:

• ~L_1 = 14~
• ~L_i = (L_{i-1}*2+2)~ ~\%~ ~1000~

Khi đi học lại, Lipon giới thiệu cho Anfel (người bạn thân nhất của Lipon) thì Anfel đã thử thách Lipon. Anfel cho Lipon ~2~ số tự nhiên ~a~ và ~b~ và bảo Lipon tính tổng các số từ số thứ ~a~ đến số thứ ~b~ của dãy số Lipon trong vòng 1 giây. Vì số ~a~ và số ~b~ mà Anfel cho quá lớn nên Lipon không thể tính nhanh được, cậu nhờ các coder giải hộ thử thách của Anfel. Là một coder tốt bụng, bạn hãy giúp Lipon nhé.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~a~ và ~b~ ~(a \le b \le 10^{16})~

Output

• Một dòng là kết quả bài toán.

Chấm điểm

• Subtask 1: ~(1 \le a \le b \le 10^3)~ (20% số điểm)
• Subtask 2: ~(10^3 < a \le b \le 10^6)~ (40% số điểm)
• Subtask 3: ~(10^6 < a \le b \le 10^{16})~ (40% số điểm)

Sample Input

1 10

Sample Output

1348