Kỳ thi Olympic Tin học Sinh viên toàn quốc đang đến gần. Đội tuyển nguồn của Học Công Nghệ hiện tại đang có N bạn học sinh xuất sắc. Tuy nhiên, theo quy định của Ban tổ chức, trường chỉ được phép cử đúng K bạn học sinh tham dự.Thầy giáo phụ trách đang muốn tính toán xem có bao nhiêu cách chọn ra K bạn học sinh từ N bạn trong đội tuyển nguồn để lập thành một đội tuyển chính thức.

Hai cách chọn được coi là khác nhau nếu có ít nhất một học sinh trong cách này không có mặt ở cách kia.Vì số lượng cách chọn có thể rất lớn, thầy giáo nhờ bạn viết một chương trình để tính chính xác số lượng cách chọn này.

Yêu cầu: Cho 2 số nguyên dương N và K. Hãy in ra số cách chọn K học sinh từ N học sinh

Dữ liệu vào: Một dòng duy nhất chứa 2 số nguyên N, K (1 <= N <= 60), cách nhau một khoảng trắng.

Dữ liệu ra: In ra một số nguyên duy nhất là số lượng cách chọn.

Đảm bảo rằng kết quả luôn nằm trong giới hạn kiểu dữ liệu số nguyên 64-bit có dấu.

Input 01:

5 2

Output 01:

10

Input 02:

60 30

Output 02:

118264581564861424

Để cài đặt tọa độ cho cổng dịch chuyển không gian, máy tính lượng tử cần thực hiện phép tính lũy thừa siêu lớn. Tọa độ chính là kết quả của phép tính A mũ B. Do hệ thống hiển thị bị giới hạn, bạn chỉ cần báo cáo phần dư của kết quả này khi chia cho M. Vì A và B cực kỳ lớn, vòng lặp thông thường sẽ mất hàng trăm năm để chạy xong. Hãy dùng thuật toán tối ưu để đưa ra đáp án trong chưa tới 1 giây.

Input: Một dòng chứa ba số nguyên dương A, B, M (1 <= A, B, M <= 10^18).

Output: Kết quả của A^B modulo M.

Ví dụ:

Input:

2 10 1000

Output:

24

Tại Học Công Nghệ, hệ thống cửa an ninh được bảo vệ bởi một "Bánh răng Mật mã". Bánh răng này chứa N con số nguyên phân biệt, ban đầu được sắp xếp tăng dần. Tuy nhiên, để tăng tính bảo mật, bánh răng đã được xoay đi một số vòng ngẫu nhiên, khiến cho dãy số bị đứt gãy tại một vị trí nào đó (Ví dụ: 4 5 6 1 2 3).

Hàng ngày, có Q lượt học sinh quét thẻ để vào lớp. Mỗi thẻ mang một mã số X. Hệ thống cần nhanh chóng xác định xem mã số X có nằm trên bánh răng hay không, và nếu có thì nằm ở vị trí thứ mấy (chỉ số tính từ 0). Do số lượng học sinh quét thẻ vào giờ cao điểm cực kỳ lớn, hệ thống cần phản hồi ngay lập tức. Nếu thuật toán của bạn chạy quá 1 giây, hệ thống cửa sẽ bị sập nguồn.

DỮ LIỆU VÀO:

Dòng 1: Gồm 2 số nguyên dương N và Q (1 <= N, Q <= 10^5) lần lượt là số lượng phần tử trên bánh răng và số lượt học sinh quét thẻ.

Dòng 2: Gồm N số nguyên phân biệt A[i] (-10^9 <= A[i] <= 10^9), thể hiện các con số trên bánh răng mật mã.

Q dòng tiếp theo: Mỗi dòng chứa 1 số nguyên X (-10^9 <= X <= 10^9) là mã số thẻ của một học sinh.

DỮ LIỆU RA:

In ra Q dòng, mỗi dòng là một số nguyên duy nhất: Vị trí của X trên bánh răng, hoặc in ra -1 nếu mã thẻ không tồn tại.

GIỚI HẠN THỜI GIAN: 1.0 giây.

VÍ DỤ:

Input:

5 3
4 5 1 2 3
1
3
10

Output:

2
4
-1

Cho N phân số, mỗi phân số có dạng 1/X. Thay vì tính toán trực tiếp với số thập phân, em hãy chuyển đổi mỗi phân số 1/X thành giá trị nghịch đảo của X theo mô đun 10^9+7, sau đó tính tổng của N giá trị nghịch đảo đó và lại lấy dư cho 10^9+7 một lần nữa.

Dữ liệu vào: Dòng đầu là số N. Dòng thứ hai chứa N số nguyên dương X1, X2, ..., Xn.

Kết quả ra: Tổng các phân số nghịch đảo theo mô đun 10^9+7.

Ràng buộc: 1 <= N <= 10^5; 1 <= Xi <= 10^6.

Ví dụ:

Input:

2
2 3

Output:

833333340