Dạo này, Miku phát hiện ra cô ấy có sở thích đặc biệt với các con số. Nhân ngày sinh nhật, cô ấy được tặng một dãy số ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Ban đầu, tất cả các phần tử đều có giá trị bằng ~0~. Hôm nay, cô ấy quyết định đố các bạn cùng lớp bài toán như sau:

Miku có ~q~ phép màu biến tất cả các phần tử trong khoảng chỉ định ~[l, r]~ như sau: phần tử thứ ~l~ sẽ được tăng một giá trị ~1^2 \times x~, phần tử thứ ~l + 1~ sẽ được tăng một giá trị ~2^2 \times x~, phần tử thứ ~l + 2~ sẽ được tăng một giá trị ~3^2 \times x~, ..., phần tử thứ ~r~ sẽ được tăng một giá trị ~(r - l + 1)^2 \times x~.

Nhiệm vụ của các bạn là hãy tìm ra mảng ~a~ sau ~q~ lần hô biến của Miku.

INPUT

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^7~).

Dòng thứ hai chứa số nguyên dương ~q~ (~1 \le q \le 10^7~) là số lượng truy vấn.

Dòng thứ ba gồm năm số nguyên dương ~l_1, l_2, r_1, r_2, x_{cap}~. (~1 \le l_1, l_2, r_1, r_2 \le 10^9~, ~1 \le x_{cap} \le 100~).

Các truy vấn sẽ được xây dựng như sau:

• Ban đầu, đặt ~cur_l = 0, cur_r = 0, cur_x = 0~.
• ~q~ truy vấn sẽ lần lượt được sinh ra bằng cách thực hiện lần lượt các thao tác như sau:
  • ~cur_l = (cur_l \times l_1 + l_2)~ ~\%~ ~n + 1~.
  • ~cur_r = (cur_r \times r_1 + r_2)~ ~\%~ ~n + 1~.
  • ~cur_x = (cur_x \times cur_l + cur_r)~ ~\%~ ~x_{cap} + 1~.
  • Nếu ~cur_l > cur_r~, ta đổi hai số này cho nhau.

Lúc này, truy vấn sẽ là bộ ba số (~cur_l~, ~cur_r~, ~cur_x~).

OUTPUT

Vì kết quả có thể rất lớn, hãy in ra tổng XOR của mảng ~a~, sau khi chia dư mọi phần tử cho ~10^9 + 7~.

Cụ thể hơn, hãy in ra ~(a_1~ ~\%~ ~(10^9 + 7))~ ~XOR~ ~(a_2~ ~\%~ ~(10^9 + 7))~ ~XOR~ ... ~XOR~ ~(a_n~ ~\%~ ~(10^9 + 7))~.

SAMPLE INPUT

5
4
1 2 3 4 7

SAMPLE OUTPUT

176

~XOR~ của cả mảng này là ~176~.

SUBTASKS