Du lịch săn vàng
Ballarat là một thành phố nằm ở bang Victoria, cách thành phố Melbourne khoảng 100km về phía Tây. Trong quá khứ, Ballarat vô cùng nổi tiếng với hoạt động khai thác vàng diễn ra rầm rộ, biến nơi đây từ một thị trấn vắng vẻ nghèo nàn nhanh chóng trở nên giàu có sầm uất chỉ trong một thời gian ngắn. Mỏ vàng đầu tiên được tìm thấy ở Mũi đất Poverty vào năm 1851. Từ đó, người ta bắt đầu tìm ra những cánh đồng vàng và hoạt động khai thác vàng đã diễn ra khắp nơi trong thị trấn. Trong những năm này, vàng ở Ballarat có sản lượng rất lớn, chiếm đến 1/3 tổng số lượng vàng được sản xuất ra trên toàn thế giới. Sau đó, đến năm 1920, mỏ vàng Ballarat bắt đầu cạn kiệt. Hiện nay, thị trấn Ballarat được bảo vệ nguyên vẹn và trở thành một “bảo tàng ngoài trời” để phục vụ khách du lịch.
Vào năm 1970, đồi mỏ vàng Sovereign chính thức mở cửa đón du khách tham quan và dần trở thành biểu tượng du lịch của Australia. Hơn nửa diện tích của khu đồi đã trở thành bảo tàng sống ngoài trời với nhiều hoạt động vẫn còn giữ nguyên như nhà máy xử lý lọc vàng, tháp cao đổ đất đá moi lên từ mỏ vàng, hệ thống thủy cục đãi vàng,… tất cả đều được gìn giữ để du khách tham quan.
An sau khi đi du lịch đến Ballarat đã được tham gia một gameshow đặc biệt. Trước mặt cậu là $N$ mỏ vàng. Mỗi mỏ vàng có trữ lượng là $M$. Tại mỗi mỏ vàng, có thể khai thác hết hoặc không khai thác. Cậu cần đoán đúng số cách khai thác vàng sau khi chia lấy dư cho $10^9+7$ từ $N$ mỏ này sao cho trữ lượng thu được đúng bằng $K$.
Hãy giúp An tìm câu trả lời đúng.
Dữ liệu
- Một dòng duy nhất chứa ba số nguyên $N,M,K \ (1 \le N,M,K \le 10^5)$.
Kết quả
- Kết quả bài toán.
Ví dụ
Ví dụ 1
input
3 2 3
output
7
Ví dụ 2
input
3 127 340
output
903
Comments