Bạn Thắng là sinh viên ngành Trí tuệ nhân tạo của một trường đại học đang nghiên cứu về các mô hình ngôn ngữ lớn (Large Language Models – LLM) như ChatGPT. Để kiểm tra độ chính xác và tốc độ tính toán của mô hình ChatGPT này, bạn Thắng đã hỏi ChatGPT kết quả của bài toán dưới đây:

~S = (1^{(2^k)} + 2^{(2^k)} + 3^{(2^k)} + \dots + n^{(2^k)}) \pmod{10}~, với ~mod~ là phép toán chia lấy dư.

ChatGPT đã nhanh chóng cho Thắng câu trả lời, tuy nhiên bạn ấy muốn kiểm tra lại kết quả xem liệu ChatGPT đã tính toán đúng chưa. Bạn hãy giúp Thắng tính ~S~ để kiểm chứng nhé!

Yêu cầu: Cho hai số nguyên dương ~n, k~. Hãy tìm ~S~.

Input

• Gồm một dòng duy nhất chứa hai số nguyên dương ~n, k~ (~1 \le n, k \le 10^{18}~).

Output

• Ghi ra một số ~S~ duy nhất.

Sample Input 1

1 3

Sample Output 1

4