Lan và Kiều là hai kiến trúc sư trẻ, họ đang thiết kế một thành phố mới.

Trong thành phố này có N con phố, trên mỗi con phố có M vị trí có thể xây nhà (mỗi vị trí chỉ xây được một ngôi nhà). Chi phí xây một ngôi nhà là 1 đồng, Lan và Kiều có tổng cộng K đồng ngân sách xây dựng.

Bây giờ, họ muốn biết có tổng cộng bao nhiêu phương án xây dựng thỏa mãn các yêu cầu sau:

1. Trên mỗi con phố phải xây ít nhất một ngôi nhà.
2. Tổng chi phí xây dựng không được vượt quá K đồng.

Vì số phương án có thể rất lớn, họ chỉ cần in ra kết quả lấy dư theo mô-đun 10⁹+7.

Dữ liệu vào

Một dòng gồm ba số nguyên N, M (1 ≤ N, M ≤ 50) và K (1 ≤ K ≤ N·M), lần lượt biểu thị số con phố, số vị trí trên mỗi con phố và ngân sách.

Dữ liệu ra

Một số nguyên, biểu thị số phương án xây dựng thỏa mãn điều kiện, lấy dư theo mô-đun 10⁹+7.

Ví dụ

Input

2 3 5

Output

8

Ghi chú

Giải thích ví dụ

N=2, M=3, K=5. Có tổng cộng 2 con phố, mỗi phố có 3 vị trí, mỗi phố phải có ít nhất 1 ngôi nhà.

• Phố thứ nhất: có thể xây 1, 2 hoặc 3 ngôi nhà
• Phố thứ hai: có thể xây 1, 2 hoặc 3 ngôi nhà
• Tổng số nhà không vượt quá 5, nên các phương án thỏa mãn điều kiện là: 1+1,1+2,1+3,2+1,2+2,2+3,3+1,3+2, tổng cộng 8 phương án.

Giới hạn dữ liệu

• 1 ≤ N, M ≤ 50
• 1 ≤ K ≤ N·M