Lớp học Competitive Programming của thầy Kiên có học sinh được đánh số từ tới . Trước mỗi giờ học, thầy Kiên yêu cầu các học sinh xếp thành một hàng theo đúng thứ tự từ tới (học sinh thứ đứng tại vị trí thứ ) trước cửa lớp.
Tuy nhiên, trong lớp của thầy Kiên cũng có những bạn học sinh rất nghịch ngợm, thường xuyên phá hàng và chen lấn xô đẩy khiến cho vị trí đứng của nhiều bạn không đúng so với yêu cầu. Nhận thấy do thầy Kiên chiều các em quá nên các em hư, thầy Kiên yêu cầu các học sinh mỗi ngày phải xếp hàng sao cho có đúng học sinh đứng đúng vị trí của mình.
Nói cách khác, một hoán vị (xếp ở vị trí là học sinh mang số thứ tự ) được thầy Kiên chấp nhận nếu tồn tại đúng giá trị sao cho:
;
#a_i = i$.
Sau khi đặt ra yêu cầu cho các học trò, thầy Kiên tự hỏi bản thân có bao nhiêu hoán vị thỏa mãn điều kiện trên. Nhưng đó là câu hỏi cho thầy Kiên, còn câu hỏi cho các bạn thí sinh VNU-OI hôm nay là tìm hoán vị thỏa mãn điều kiện trên có thứ từ điển thứ .
Một cách rõ ràng hơn, nếu ta sắp xếp các hoán vị thỏa mãn tăng dần theo thứ tự từ điển, kết quả của bài toán sẽ là hoán vị thứ trong danh sách.
Dữ liệu vào:
Gồm một dòng duy nhất chứa ba số nguyên và .
Dữ liệu ra:
In ra một dòng duy nhất chứa hoán vị thứ theo thứ tự từ điển thỏa mãn điều kiện của Kiên. Nếu số lượng hoán vị thỏa mãn nhỏ hơn , in ra .
