Phần thưởng

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, $\dots$, 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 (điền hết hàng $1$ từ cột $1$ đến cột $n$, rồi đến hàng $2$, $\dots$). Ô 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.

Dữ liệu vào

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

Dữ liệu ra

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

Ràng buộc

• $1\le m,n\le {10}^9$.
• $1\le k\le 10$.
• $1\le x\le u\le m$, $1\le y\le v\le n$.

Subtasks

• Có $30\%$ số test ứng với $30\%$ số điểm của bài có $m=1$ và $n\le 10$;
• Có $20\%$ số test khác ứng với $20\%$ số điểm của bài có $m=1$ và $n\le {10}^3$;
• Có $20\%$ số test khác ứng với $20\%$ số điểm của bài có $m=1$, $n\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ó $m=1$ và $n\le {10}^9$;
• Có $10\%$ số test còn lại ứng với $10\%$ số điểm còn lại của bài có $m,n\le {10}^9$.

Ví dụ