Nam là một học sinh rất thích sáng tạo trong việc học môn Toán. Khi học về bài dãy số, Nam nghĩ ra một dãy số (~a_n~) mà cậu ta gọi là dãy đặc biệt được xây dựng theo quy tắc sau:

• Cho trước số ~a_0~ là số tự nhiên có tối đa ~10~ chữ số.
• Số ~a_i~ ~(i \ge 1)~ là một số tự nhiên nhận được từ ~a_{i-1}~ bằng cách viết thêm vào sau các chữ số của ~a_{i-1}~ chính ~a_{i-1}~ nhưng viết theo thứ tự ngược lại.

Chẳng hạn: ~a_0 = 345, a_1 = 345543, a_2 = 345543345543, \dots~

Nam rất thích dãy số này và đem khoe nó với các bạn. Hoàng là một thành viên trong lớp cảm thấy thích thú với dãy số đặc biệt này. Sau một lúc suy nghĩ, Hoàng liền đố Nam một bài toán sau: "Với hai số nguyên dương ~N~ và ~K~ cho trước, hãy tìm chữ số thứ ~K~ của số hạng ~a_N~ trong dãy đặc biệt trên".

Bạn hãy giúp Nam lập trình giải bài toán này nhé.

Yêu cầu: Cho trước ~a_0~, ~N~ và ~K~. Hãy tìm chữ số thứ ~K~ của số hạng ~a_N~.

Input

• Dòng đầu ghi số tự nhiên ~a_0~ ~(a_0\le 10^{10^5})~.
• Dòng thứ hai ghi hai số nguyên dương ~N~, ~K~ ~(1\le N\le 63,\ 1\le K\le 10^{18})~, các số cách nhau ít nhất một dấu cách.

Output

Ghi ra chữ số tìm được. Trong trường hợp không tìm được chữ số nào thì ghi ra ~-1~.

Sample Input 1

345
2 10

Sample Output 1

5

Subtasks

• Subtask 1: ~60\%~ test có ~N \le 20~;
• Subtask 2: ~40\%~ test không có ràng buộc gì thêm.

Hãy đếm xem có bao nhiêu mảng khác nhau ~a_1, a_2, \dots, a_n~ trong đó ~a_i~ nhận các giá trị nguyên dương trong đoạn ~[1,M]~ sao cho tồn tại ít nhất một đoạn ~K~ giá trị liên tiếp giống nhau?

Ở đây hai mảng được gọi là khác nhau nếu như tồn tại ít nhất một vị trí mà giá trị phần tử hai mảng ở vị trí này là khác nhau.

Input

• Một dòng duy nhất chứa ba số nguyên dương ~n,M,K\ (1\le n,M,K\le 10^6)~.

Output

• Một số nguyên duy nhất là số lượng mảng khác nhau tìm được. Con số này có thể rất lớn nên bạn chỉ cần lấy phần dư của nó khi chia cho ~10^9+7~.

Sample Input 1

3 2 2

Sample Output 1

6

Giải thích: Các mảng tìm được là ~(1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 1, 1), (2, 2, 1), (2, 2, 2)~.