Tương truyền câu chuyện cổ, một mưu sĩ thách đấu với nhà vua về việc cung cấp số thóc bằng cách đặt số thóc vào các ô trong bàn cờ quen thuộc. Bài toán như sau: bàn cờ có 8x8 ô, đặt 1 hạt thóc vào ô thứ nhất, ta đặt vào ô thứ hai số hạt thóc gấp đôi ô thứ nhất, tiếp tục đặt vào ô thứ ba số hạt thóc gấp đôi ô thứ hai,… Như vậy số hạt thóc ở ô thứ 64 là một con số rất lớn, 2⁶³ hạt thóc.

Lần thử thách này được nâng cấp hơn: Ta đặt 1 hạt thóc vào ô thứ nhất, ta đặt vào ô thứ hai số hạt thóc gấp k lần số hạt thóc ở ô thứ nhất, ta tiếp tục đặt vào ô thứ ba số hạt thóc gấp k lần số hạt thóc ở ô thứ hai,… Đặc biệt, số ô của bàn cờ lên đến 10⁹ x 10⁹ ô. Do kết quả có thể là số rất lớn, nên bạn chỉ cần tìm ra chữ số hàng đơn vị của tổng số hạt thóc từ ô thứ nhất đến ô thứ N.

Input:

- Dòng thứ nhất: một số nguyên dương duy nhất k thể hiện số hạt thóc ở ô thứ hai, kể từ ô thứ hai trở đi, số thóc ở ô hiện tại sẽ gấp số thóc ở ô liền trước nó đúng k lần (1 ≤ k ≤ 10¹⁸).

- Dòng thứ hai: một số nguyên dương duy nhất N thể hiện ô số cần tính đến. (1 ≤ N ≤ 10¹⁸).

Output: một số nguyên duy nhất thể hiện chữ số hàng đơn vị của tổng số hạt thóc từ ô thứ nhất đến ô thứ N.

Ví dụ:

Ràng buộc: Thời gian chạy 0.5 giây, trong đó:

- 10/20 số test với dữ liệu 1 ≤ k ≤ 10⁴, 1 ≤ N ≤ 10⁴.

- 7/20 số test với dữ liệu 1 ≤ k ≤ 10⁶, 1 ≤ N ≤ 10⁶.

- 3/20 số test với dữ liệu 10⁶ ≤ k ≤ 10¹⁸, 10⁶ ≤ N ≤ 10¹⁸.