Số học luôn là một lĩnh vực quyến rũ với các định lý đẹp, và đôi khi cũng nguy hiểm chết người. Có những tính chất ta nghĩ là dễ nhưng biến đổi thử mới thấy khó, nhưng đôi khi ngược lại, có những kết quả khá hiển nhiên mà ta thường tìm tòi những thứ rất xa xôi.

Do biết team ICPC của H3.2 cũng rất thích số học, đặc biệt là những bài đố mẹo, đố vui nên hôm nay, thầy Luna có giới thiệu một bài như sau: cho số nguyên dương ~n, m~, hỏi số ~n^{m!}~ thì chia cho ~2024~ dư mấy? Bạn hãy thử sức với bài toán đố vui này nhé.

Input

Một dòng duy nhất gồm hai số nguyên dương ~n, m~ với ~1 \le n, m \le 10^{18}~.

Output

Kết quả của bài toán.

Sample input 1

3 2

Sample output 1

9

Sample input 2

2023 100000

Sample output 2

1

Subtasks

• Có 25% test ứng với ~n, m \le 15~.
• Có 25% test ứng với ~m \le 15~.
• Có 50% test với giới hạn tùy ý.