Một virus mới đã xâm nhập vào hệ thống máy của Ban tổ chức. Loại virus này sau \(1\) giây từ lúc nó sinh ra sẽ tự tạo thêm \(K\) virus nữa. Tuy nhiên, virus chỉ có thể tự tạo thêm \(1\) lần, sau đó nó sẽ đi phá hủy dữ liệu trong máy tính nên không tự sinh ra tiếp.

Ví dụ: với \(K = 2\) thì sau giây thứ \(1\) virus \(A\) ban đầu tạo ra virus \(B, C\). Sau giây thứ \(2\) thì virus \(B, C\) sẽ tạo ra virus \(B_1, B_2, C_1, C_2\) nên tổng số virus là \(7\). Sau giây thứ \(3\) thì \(4\) virus \(B_1, B_2, C_1, C_2\) sẽ tạo ra thêm virus nữa nên tổng số là \(15\).

Tại từng thời điểm số virus sẽ như sau:

Hãy giúp BTC tính số lượng virus sau giây thứ \(N\).

Input

• Dòng đầu tiên chứa số tự nhiên \(N\) là số giây kể từ lúc có virus (\(1 \le N \le 10^{15}\)).
• Dòng thứ hai chứa số tự nhiên \(K\) là số lượng virus tự sinh thêm sau một giây (\(1 \le K \le 9\)).

Output

• Gồm một dòng chứa một số tự nhiên là chữ số cuối cùng của số lượng virus sau giây thứ \(N\).

Example

2
2

7

4
3

1

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \le 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(10 < N \le 1000\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.