#1354. PIANO2 - Đàn PIANO kỳ lạ

BT bắt đầu học đánh đàn piano. Đàn piano của anh ta có phím bấm. Phím thứ khi bấm sẽ tạo ra âm thanh có tần số . Khi BT đánh đàn piano, anh ta bấm đồng thời đúng phím trong số phím của cây đàn. Tuy vậy, đây là cây đàn kỳ lạ. Nếu bấm cùng một lúc phím thì nó chỉ vang lên âm của phím có tần số âm thanh cao nhất. BT học chơi đàn bằng cách bấm tất cả các tổ hợp phim khác nhau có thể có. Anh ta muốn biết tổng giá trị tần số của các âm phát ra khi bấm hết các tổ hợp này. Viết một chương trình nhỏ giúp anh ta.

Dữ liệu vào:

• Dòng đầu tiên ghi hai số nguyên ;
• Dòng thứ hai chứa số nguyên .

Dữ liệu ra:

• Một số nguyên duy nhất là kết quả tìm được. Vì con số này có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho .

Ví dụ:

Dữ liệu vào:

5 3
2 4 2 3 4

Dữ liệu ra:

39

Dữ liệu vào:

5 1
1 0 1 1 1

Dữ liệu ra:

4
5 2
3 3 4 0 0

Dữ liệu ra:

31

Giới hạn:

• Subtask số điểm có ;
• Subtask Không có ràng buộc bổ sung.