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\) x \(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\) \(\leq\) \(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\) \(\leq\) \(x\) \(\leq\) \(u\) \(\leq\) \(m\) và \(1\) \(\leq\) \(y\) \(\leq\) \(v\) \(\leq\) \(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\) \(\leq\) \(i\) \(\leq\) \(u\) và \(y\) \(\leq\) \(j\) \(\leq\) \(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\) \(\leq\) \(i\) \(\leq\) \(u\) và \(y\) \(\leq\) \(j\) \(\leq\) \(v\) của bảng số được điền theo quy tắc trên.

Input

• Một dòng chứa 7 số nguyên dương \(m,\) \(n,\) \(k,\) \(x,\) \(y,\) \(u,\) \(v.\)

Output

• Một dòng chứa một số là phần dư của phép chia tổng các số được tính chia cho \(111539768.\)

Scoring

• Subtask #1 (\(30\%\) số điểm): \(m=1\) và \(n\leq 10.\)
• Subtask #2 (\(20\%\) số điểm): \(m=1\) và \(n\leq 10^3.\)
• Subtask #3 (\(20\%\) số điểm): \(m=1;\) \(n\leq 10^9\) và \(v−y\leq 10^7.\)
• Subtask #4 (\(20\%\) số điểm): \(m=1\) và \(n\leq 10^9\)
• Subtask #5 (\(10\%\) số điểm): \(m,n\leq 10^9.\)

Example

4 4 2 1 2 2 3

102

Nguồn: 2019 chính thức