Cho một bàn cờ \(m \times n\) và 1 con hậu trên bàn cờ. LN tưởng tượng mình là con hậu và muốn đặt \(k\) con vua lên bàn cờ. LN muốn \(k\) con vua ở các vị trí khác nhau và con hậu ngắm nhìn được nhiều con vua nhất. Một con vua nằm trong tầm ngắm của con hậu nếu nó 2 quân nằm trên cùng 1 hàng, cột hoặc đường chéo, đồng thời giữa chúng không có con vua nào cản đường. LN tự hỏi con hậu có thể ngắm được nhiều nhất bao nhiêu con vua. ami cảm thấy bài toán quá đơn giản nên thêm vào: Có bao nhiêu cách xếp để con hậu ngắm được nhiều con vua nhất?

Hai cách xếp được gọi là khác nhau nếu có một ô cờ mà trong cách xếp này có vua, và trong cách kia không có vua.

Input

• Dòng đầu tiên chứa 3 số nguyên dương \(m, n, k \ (1 \leq m, n \leq 1000; 1 \leq k < mn)\)

• Dòng thứ hai chứa 2 số nguyên dương \(x, y \ (1 \leq x \leq m, 1 \leq y \leq n)\) - vị trí của con hậu

Output

• In ra 2 số nguyên dương \(a, b\) trên 1 dòng. Trong đó \(a\) là số con vua tối đa LN có thể ngắm, \(b\) là số cách xếp để LN ngắm được nhiều con vua nhất sau khi \(\mod 10^9+7\)

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(m = 1\)

• Subtask \(2\) (\(10\%\) số điểm): \(m, n \leq 4\)

• Subtask \(3\) (\(10\%\) số điểm): \(m, n \leq 20; k \leq 3\)

• Subtask \(4\) (\(10\%\) số điểm): \(m, n \leq 20\)

• Subtask \(5\) (\(10\%\) số điểm): \(m, n \leq 100\)

• Subtask \(6\) (\(50\%\) số điểm): \(m, n \leq 1000\)

Example

2 2 2
1 1

2 3

3 3 4
1 1

3 28