Cho hai số nguyên dương ~a~ và ~b~. Hãy tìm chữ số tận cùng của ~a^b~.

Lưu ý rằng ~b~ có thể rất lớn nên được cho dưới dạng một xâu chữ số.

Input:

• Dòng thứ nhất chứa số nguyên ~a~.
• Dòng thứ hai chứa số nguyên ~b~ (không có số 0 vô nghĩa ở đầu).

Output:

Một chữ số duy nhất là chữ số tận cùng của ~a^b~.

Ràng buộc:

~1 \le a \le 10^9~, ~1 \le b~. Gọi ~L~ là số chữ số của ~b~.

• Subtask 1 (30% số điểm): ~L \le 6~.
• Subtask 2 (30% số điểm): ~L \le 18~.
• Subtask 3 (40% số điểm): ~L \le 10^5~.

Ví dụ:

Input

2
10

Output

4

Input

7
222222222222222222222

Output

9

Giải thích ví dụ 1: ~2^{10} = 1024~, chữ số tận cùng là ~4~.