Để chuẩn bị cho sự kiện sắp tới của trường, mỗi lớp sẽ phải chuẩn bị một tiết mục đóng kịch. Được bạn bè trong lớp tin tưởng giao phó nhiệm vụ, Loli may mắn có cơ hội vào vai trong một câu chuyện cổ tích nổi tiếng. Chiều hôm đó Loli sẽ trở thành một cô Tấm hiền lành thùy mị nết na.

Truyện Tấm Cám thì ai cũng biết rồi, câu chuyện này phản ánh những mâu thuẫn trong gia đình, đặc biệt là mối quan hệ mẹ kế - con chồng; cuộc đấu tranh giữa và cái thiện thắng cái ác của người Việt.

Nhưng trước khi diễn ra cái cuộc "đấu tranh" giữa cái thiện và cái ác, thì Loli phải làm xong một công việc khó khăn thì mới được dì ghẻ cho đi chơi lễ hội huhuhu.

Dì ghẻ cho Loli một xâu kí tự gồm ~n~ chữ số, Loli phải chia dãy thành ~k~ đoạn liên tiếp sao cho giá trị của số tạo thành ở mỗi đoạn đều chia hết cho ~p~. Các đoạn có thể có độ dài tùy ý, và có thể bắt đầu bằng một hay nhiều chũ số ~0~.

Dì ghẻ bắt Loli đếm số cách thực hiện việc phân tách này. Vì dì ghẻ có test sẵn nên có thể biết được Loli trả lời đúng hay sai. Cũng vì Loli không được động vào dàn máy gaming của Cám ở nhà nên đành nhờ bạn code giúp.

Input

• Dòng đầu tiên chứa ba số nguyên ~n~, ~k~ và ~p~ ~(1 \le n \le 50000, 1 \le k \le 200, 1 \le p \le 30)~.
• Dòng thứ hai chứa dãy gồm ~n~ chữ số, từ ~0~ đến ~9~.

Output

• Gồm một số nguyên duy nhất là số cách chia dãy ~n~ chữ số thành ~k~ đoạn sao cho giá trị của mỗi đoạn đều chia hết cho ~p~.
• Do kết quả có thể rất lớn, cần in ra kết quả theo modulo ~10^9+7~.

Subtask

• Subtask 1 (~15\%~ điểm): ~p = 1~
• Subtask 2 (~15\%~ điểm): ~p = 2~
• Subtask 3 (~15\%~ điểm): ~p = 3~
• Subtask 4 (~15\%~ điểm): ~n \le 50~ và ~k \le 5~
• Subtask 5 (~15\%~ điểm): ~n \le 500~ và ~k \le 20~
• Subtask 6 (~15\%~ điểm): ~n \le 5000~
• Subtask 7 (~10\%~ điểm): Không có ràng buộc gì thêm.

Sample Input 1

4 2 3
9756

Sample Output 1

2

Sample Input 2

5 3 2
00000

Sample Output 2

6

Giải thích

• Trong ví dụ đầu tiên, có hai cách chia thỏa mãn là ~(9, 756)~ và ~(975, 6)~. Hai cách chia đoạn ~(9756)~ và ~(9, 75, 6)~ không thỏa mãn vì có ít hơn hoặc nhiều hơn hai đoạn, cách chia ~(97, 56)~ không thỏa mãn vì ~97~ không chia hết cho ~3~.
• Trong ví dụ thứ hai, các cách chia thỏa mãn là ~(0, 0, 000)~, ~(0, 000, 0)~, ~(000, 0, 0)~, ~(0, 00, 00)~, ~(00, 0, 00)~ và ~(00, 00, 0)~.