Solving the problem of computer science, Vova has once again made a mistake. He again brought up in the output file number, forgetting to separate them by spaces. Seeing the result, Vova was upset at first, and then pondered the following question: how many there are different sequences of integers, such that if you write them with no spaces, one obtains the same result as that of him. He also remembered that his program was able to deduce not arbitrary numbers, but only those that do not exceed \textbf{C} and have no leading zeros. To answer the question, Vova decided to write a program that will allow him to find a number of different sequences of integers, each of which any number does not exceed \textbf{C}. He understood that this number could be quite large, so restrict your search to the last \textbf{k} digits of this number. Need to write a program that will Vova, how can they correctly solve the problem. \InputFile The first line of the input file contains three integers --- \textbf{n}, \textbf{C} and \textbf{k} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50000}, \textbf{1} ≤ \textbf{C} ≤ \textbf{10^8}, \textbf{1} ≤ \textbf{k} ≤ \textbf{18}). In the second line of this file contains the result of Vovinam program, consisting of \textbf{n} digits. \OutputFile In the output file print out the last \textbf{k} digits of the desired number of sequences without leading zeros.