Order
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 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 0, 5, 6, and even 0 and 7, the first few numbers would look like this:: 0, 5, 6, 70, 75, 76, 500, 505, 506, 570, 575, 576, 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 1.
Input
The first line contains three numbers N, K, L. N - requested an official number, K and 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.
1 ≤ N ≤ 10^55, 2 ≤ K, L ≤ 10.
Output
The output file is the only string containing the response to the problem. It is guaranteed that the answer is in the range 2^64-1.