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

b Hãy đếm số cách xếp các viên bi vào bảng \(M × N\) sao cho trên mỗi dò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 ô khác loại. 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\).

Dữ liệu:

• Một dòng duy nhất ghi 3 số nguyên dương \(M, N, k\). Các số được ghi cách nhau bởi dấu cách.

Kết quả:

• Ghi số cách xếp thỏa mãn yêu cầu bài toán

Sample Input

1 2 1

Sample Output

16

Ràng buộc

• Có 30% test với \(M = 1; N ≤ 30; k = 1\)

• Có 30% test với \(1 ≤ M, N ≤ 10^3; 1 ≤ k ≤ 4\)

• Có 40% test với \(1 ≤ M, N ≤ 10^6; 1 ≤ k ≤ 4\)