Khang rất thích hai chữ số 8 và 6 vì anh ấy quan niệm rằng chữ số 8 là Phát còn chữ số 6 là Lộc.

Nhân dịp đầu xuân Bính Ngọ 2026, Khang dành riêng cho Team HĐK 2026 một bài tập về Phát Tài Phát Lộc như sau:

Với số khởi đầu là 86 (Phát Lộc), với mỗi lần biến đổi theo qui tắc sau:

• Lấy số nhân cho 8 rồi cộng cho 6
• Sau đó lấy số mod cho \(m\) \((2 \leq m \leq 100000)\)

Input

• Dòng 1: số nguyên dương \(n\) \((1 \leq n \leq 10^{12})\)
• Dòng 2: số nguyên dương \(m\) \((2 \leq m \leq 100000)\)

Output

In ra trên 2 dòng:

• Dòng 1: số nhận được sau lần biến đổi thứ \(n\)
• Dòng 2: tổng các số đã biến đổi từ lần thứ 1 đến lần biến đổi thứ \(n\)

Example

3
88866

44470
50722

100
88666

46322
4055392