Xếp bi

Cho một bảng hình chữ nhật kích thước $M\times N$ ($M$ hàng, $N$ cột) và $4$ loại bi: xanh, đỏ, tím, vàng với số lượng không giới hạn.

Yêu cầu: Hãy đếm số cách xếp các viên bi vào bảng $M\times N$ sao cho mỗi ô chứa đúng một viên bi và trên mỗi hàng phải có ít nhất $k$ loại bi khác nhau, biết rằng hai cách xếp được gọi là khác nhau nếu có ít nhất một ô chứa hai loại bi khác nhau trong hai cách xếp đó.

Vì số cách rất lớn nên chỉ cần in ra phần dư của kết quả khi chia cho ${10}^9+7$. Nếu không có cách xếp nào thỏa mãn (chẳng hạn khi $k>N$) thì in ra $0$.

Dữ liệu vào

Một dòng duy nhất gồm ba số nguyên dương $M$, $N$, $k$, các số được ghi cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất là số cách xếp thỏa mãn yêu cầu, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le M,N\le {10}^6$.
• $1\le k\le 4$.
• Có $30\%$ số test với $M=1$, $N\le 30$, $k=1$.
• Có $30\%$ số test với $1\le M,N\le {10}^3$, $1\le k\le 4$.
• Có $40\%$ số test với $1\le M,N\le {10}^6$, $1\le k\le 4$.

Ví dụ