In some institutions, the documents are numbered in a strange way. One set of figures is used for odd bits and, in general, a different set for the even bits (bits are numbered from right to left starting from \textbf{1}). Moreover, in different years can be used by different sets of digits. The only thing that is strictly adhered to in this place - is the fact that the numbers in the given constraints are not dropped and preserve order in ascending order. For example, if the odd digits using the numbers \textbf{0}, \textbf{5}, \textbf{6}, and even \textbf{0} and \textbf{7}, the first few numbers would look like this:: \textbf{0}, \textbf{5}, \textbf{6}, \textbf{70}, \textbf{75}, \textbf{76}, \textbf{500}, \textbf{505}, \textbf{506}, \textbf{570}, \textbf{575}, \textbf{576}, \textbf{600}, ... We need to write a program that for a given set of numbers for the even and odd positions and the known document number assigned to him under the conditions described, to determine its serial number, measured from \textbf{1}. \InputFile The first line contains three numbers \textbf{N}, \textbf{K}, \textbf{L}. \textbf{N} - requested an official number, \textbf{K} and \textbf{L} - respectively the number of digits used in odd and even positions. In the second row are separated by a space figures used in odd positions, and in the third line - the figures used in the even positions. \textbf{1} ≤ \textbf{N} ≤ \textbf{10^55}, \textbf{2} ≤ \textbf{K}, \textbf{L} ≤ \textbf{10}. \OutputFile The output file is the only string containing the response to the problem. It is guaranteed that the answer is in the range \textbf{2^64-1}.