Theo truyền thuyết, vua Sêram rất khâm phục và đã tặng thưởng cho nhà thông thái Sêta vì đã sáng tạo ra cờ vua. Phần thưởng mà Sêta mong muốn là tất cả các hạt lúa mì đặt trên bàn cờ theo quy tắc sau: Ô thứ nhất đặt một hạt, ô thứ hai đặt 2 hạt, ô thứ ba đặt 4 hạt, ... , tiếp tục theo quy luật ô sau có số hạt gấp đôi số hạt của ô trước, cho tới khi đặt đến ô thứ 64 trên bàn cờ vua. Rất thích thú với truyền thuyết này, Long và Vân cùng nhau giải quyết bài toán sau:

Xét một bảng số kích thước ~m \times n~, các hàng được đánh số từ 1 đến ~m~ từ trên xuống dưới, các cột được đánh số từ 1 đến ~n~ từ trái sang phải. Ô nằm giao giữa hàng ~i~ và cột ~j~ được gọi là ô ~(i, j)~. Với một số nguyên dương ~k~ (~k \le 10~), lần lượt điền các số vào các ô của bảng theo nguyên tắc sau:

• Bắt đầu điền từ ô (1,1) ghi số 1;
• Điền lần lượt từng ô từ trên xuống dưới, từ trái qua phải. Ô tiếp theo điền giá trị gấp ~k~ lần giá trị điền ô trước.

Với bộ 4 số nguyên dương ~(x, y, u, v)~ thỏa mãn ~1 \le x \le u \le m~ và ~1 \le y \le v \le n~, hai bạn Long và Vân muốn tính tổng các số nằm trong các ô ~(i, j)~ mà ~x \le i \le u~ và ~y \le j \le v~.

Yêu cầu: Cho 7 số nguyên dương ~m, n, k, x, y, u, v~, hãy tính tổng các số nằm trong các ô ~(i, j)~ mà ~x \le i \le u~ và ~y \le j \le v~ của bảng số được điền theo quy tắc trên.

Input

• Gồm một dòng chứa 7 số nguyên dương ~m, n, k, x, y, u, v~.

Output

• Ghi một số là phần dư của phép chia tổng các số được tính chia cho 111539768.

Sample Input 1

4 4 2 1 2 2 3

Sample Output 1

102

Subtasks

• Có 30% số test ứng với 30% số điểm của bài có ~k = 1~ và ~m, n \le 10~;
• Có 20% số test khác ứng với 20% số điểm của bài có ~k = 1~ và ~m, n \le 10^3~;
• Có 20% số test khác ứng với 20% số điểm của bài có ~k = 1; m \le 10^9~ và ~v - y \le 10^7~;
• Có 20% số test khác ứng với 20% số điểm của bài có ~k = 1~ và ~m, n \le 10^9~;
• Có 10% số test còn lại với 10% số điểm còn lại của bài có ~m, n \le 10^9~.