Alice muốn gửi cho Bob một con số bí mật. Tuy nhiên, việc gửi theo cách thông thường rất dễ bị tin tặc tấn công. Tình cờ thay, hôm nay Alice được biết đến dãy số Fibonacci được định nghĩa như sau:

• ~f_n = 1~ với ~1 \le n \le 2~.
• ~f_n = f_{n-1}+f_{n-2}~ với ~n > 2~.

Với ý tưởng từ dãy Fibonacci, Alice đã tạo ra một dãy ~m~ như sau:

• ~m_1 = a, m_2 = b, m_3 = c~.
• ~m_n = m_{n-1} \oplus m_{n-2} \oplus m_{n-3}~ với ~n > 3~, với ~\oplus~ là phép toán thao tác bit XOR.

Con số của Alice gửi cho Bob sẽ là giá trị ~m_l + m_{l + 1} + ... + m_r~. Alice sẽ gửi cho Bob bộ năm số ~(a, b, c, l, r)~. Bạn hãy giúp Bob tìm ra con số mà Alice muốn gửi nhé.

Dữ liệu

• ~5~ số nguyên dương ~a, b, c, l, r~ ~(1 \le a, b, c, l, r \le 10^{12}; l \le r)~.

Kết quả

• In ra phần dư của con số bạn tìm được khi chia cho ~1234567891~.

Ví dụ

Dữ liệu

1 2 3 4 5

Kết quả

1

Giải thích

• Dựa vào quy luật của dãy số, dễ dàng tính ~m_4 = 0, m_5 = 1~. Từ đó ta có con số mà Alice muốn gửi là ~m_4 + m_5 = 1~.