Chúng ta có một lưới vuông với \(N\) hàng và \(M\) cột. Gọi \((i,j)\) là ô ở hàng thứ \(i\) từ trên xuống và cột thứ \(j\) từ trái sang. Chúng ta sẽ chọn \(K\) ô và đặt một mảnh trên mỗi ô.

Nếu chúng ta đặt \(K\) mảnh trên các ô \((x_1, y_1), (x_2, y_2), ...,\) và \((x_K, y_K)\), chi phí của cách sắp xếp này được tính như sau:

\[\sum_{i=1}^{K-1} \sum_{j=i+1}^{K} (\|x_i - x_j\| + \|y_i - y_j\|)\]

Tìm tổng chi phí của tất cả các cách sắp xếp có thể của các mảnh. Vì giá trị này có thể rất lớn, hãy in kết quả theo modulo \(10^9 + 7\).

Chúng ta coi hai cách sắp xếp của các mảnh là khác nhau nếu và chỉ nếu có một ô chứa mảnh trong một cách sắp xếp nhưng không chứa mảnh trong cách sắp xếp khác.

Ràng buộc

• Tất cả các giá trị đầu vào là số nguyên.
• \(2 \leq N \times M \leq 2 \times 10^5\)
• \(2 \leq K \leq N \times M\)

INPUT FORMAT

Đầu vào được cung cấp từ Standard Input theo định dạng sau:

N
M
K

OUTPUT FORMAT

In ra tổng chi phí của tất cả các cách sắp xếp có thể của các mảnh, theo modulo \(10^9 + 7\).

Ví dụ:

Input

2 2 2

Output

8

Có sáu cách sắp xếp có thể của các mảnh, như sau:

• \(((1,1),(1,2))\), với chi phí \(\|1-1\| + \|1-2\| = 1\)
• \(((1,1),(2,1))\), với chi phí \(\|1-2\| + \|1-1\| = 1\)
• \(((1,1),(2,2))\), với chi phí \(\|1-2\| + \|1-2\| = 2\)
• \(((1,2),(2,1))\), với chi phí \(\|1-2\| + \|2-1\| = 2\)
• \(((1,2),(2,2))\), với chi phí \(\|1-2\| + \|2-2\| = 1\)
• \(((2,1),(2,2))\), với chi phí \(\|2-2\| + \|1-2\| = 1\)

Tổng các chi phí này là \(8\).

Input

4 5 4

Output

87210

Giải thích ví dụ mẫu

Ví dụ 1:

• Input:

  2 2 2

• Giải thích:

  • Có 6 cách sắp xếp hai ô với tổng chi phí là 8, tính từ các khoảng cách giữa các ô.

Ví dụ 2:

• Input:

  4 5 4

• Giải thích:

  • Tổng chi phí cho tất cả các cách sắp xếp 4 ô trong lưới 4x5 là 87210, được tính từ các khoảng cách giữa các ô.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House