Cho các số nguyên \(n, k, \alpha, \beta\).

Gọi \(A_{0}\) là một ma trận vuông có kích thước \(n \times n\), các hàng được đánh số từ \(1\) đến \(n\), các cột được đánh số từ \(1\) đến \(n\), ô ở hàng \(i\) cột \(j\) được gọi là ô \(A_{0}(i, j)\) và giá trị tại ô \(A_{0} (i, j)\) là \(A_{0} (i, j) = i^{\alpha} \times j^{\beta}\).

Gọi \(B_{0}\) là một ma trận vuông có kích thước \(n \times n\), các hàng được đánh số từ \(1\) đến \(n\), các cột được đánh số từ \(1\) đến \(n\), ô ở hàng \(i\) cột \(j\) được gọi là ô \(B_{0}(i, j)\) và giá trị tại ô \(B_{0} (i, j)\) là \(B_{0} (i, j) = A_{0} (j, i)\).

Với mọi số nguyên không âm \(x\) \((x \geq 0)\), ma trận \(A_{x + 1}\) là một ma trận có kích thước \({3^{x + 1}}n \times {3^{x + 1}}n\) và có dạng như sau

Ma trận \(B_{x + 1}\) là một ma trận có kích thước \(3^{x + 1}n \times 3^{x + 1}n\) và \(B_{x + 1} (i, j) = A_{x + 1} (j, i)\) \(\forall 1 \leq i, j \leq 3^{x + 1}n\).

Hình chữ nhật con \((u, v, x, y)\) của một ma trận là tập hợp các ô \((i, j)\) mà \(u \leq i \leq x, v \leq j \leq y\).

Yêu cầu: Cho bốn số nguyên \(n, k, \alpha, \beta\). Hãy tính tổng giá trị của các ô trong hình chữ nhật con \((u, v, x, y)\) của ma trận \(A_{k}\). Vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư khi chia kết quả cho \(({10}^9 + 7)\).

Input

• Dòng đầu tiên gồm một số nguyên dương \(T\) \((1 \leq T \leq 100)\) là số bộ dữ liệu.
• \(T\) nhóm dòng sau, mỗi nhóm dòng biểu diễn một bộ dữ liệu:
  • Dòng đầu tiên chứa bốn số nguyên \(n, k, \alpha\) và \(\beta\) \((1 \leq n \leq 10^{9}, 0 \leq k \leq 10, 1 \leq \alpha, \beta \leq 100)\).
  • Dòng thứ hai gồm bốn số nguyên \(u, v, x, y\) \((1 \leq u \leq x \leq n \times 3^{k}, 1 \leq v \leq y \leq n \times 3^{k})\) thể hiện câu hỏi cần trả lời.

Output

• Gồm \(T\) dòng, mỗi dòng gồm một số nguyên là kết quả của các bộ dữ liệu.

Scoring

• Subtask \(1\) (\(7\%\) số điểm): \(T \leq 5, n \leq 30, k \leq 3\).
• Subtask \(2\) (\(8\%\) số điểm): \(n = 1\).
• Subtask \(3\) (\(9\%\) số điểm): \(n = 2\).
• Subtask \(4\) (\(10\%\) số điểm): \(T \leq 5\) và \(k \leq 4\) và \(n \leq {10}^5\).
• Subtask \(5\) (\(11\%\) số điểm): \(T \leq 5\) và \(k \leq 4\) và \(1 \leq \alpha, \beta \leq 2\).
• Subtask \(6\) (\(12\%\) số điểm): \(T \leq 5\) và \(k \leq 4\) và \(\alpha = \beta = 3\).
• Subtask \(7\) (\(13\%\) số điểm): \(T \leq 5\) và \(k \leq 4\).
• Subtask \(8\) (\(14\%\) số điểm): \(\alpha, \beta \leq 10\).
• Subtask \(9\) (\(16\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
2 1 1 2
2 2 5 5
10 3 2 2
3 8 65 15

60
708000