{"code":"hs5f","name":"LN ngắm trai","description":"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. [user: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? \r\n\r\nHai 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.\r\n\r\n#### Input\r\n\r\n- 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)$\r\n\r\n- 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\r\n\r\n#### Output\r\n\r\n- 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$\r\n\r\n#### Scoring\r\n\r\n- Subtask $1$ ($10\\%$ số điểm): $m = 1$\r\n\r\n- Subtask $2$ ($10\\%$ số điểm): $m, n \\leq 4$\r\n\r\n- Subtask $3$ ($10\\%$ số điểm): $m, n \\leq 20; k \\leq 3$\r\n\r\n- Subtask $4$ ($10\\%$ số điểm): $m, n \\leq 20$\r\n\r\n- Subtask $5$ ($10\\%$ số điểm): $m, n \\leq 100$\r\n\r\n- Subtask $6$ ($50\\%$ số điểm): $m, n \\leq 1000$\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        2 2 2\r\n        1 1\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        2 3\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n\r\n        Trong test ví dụ đầu tiên, có 2 con vua và có thể đặt chúng vào 3 vị trí. Bất kể có đặt thế nào thì LN vẫn ngắm được 2 con vua. Số cách đặt là $C^2_3=3$\r\n\r\n!!! question \"Test 2\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        3 3 4\r\n        1 1\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        3 28\r\n        ```","points":600.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}