Numbers in Wonderland

An N-digit number, without leading zeros, is called a Mirrorland number if it can be written with its digits displayed as they appear on electronic displays (refer to the illustration), and when held up to a mirror, the number appears unchanged. All digits must be fully visible in the mirror, undistorted, and the entire number must be readable from left to right. The only potential difference is the spacing between the digits.

Vasya has written down some digits of an N-digit number on paper, with certain positions already fixed. Your task is to help him determine how many different Mirrorland numbers he can create by filling in the remaining positions with all possible valid digits.

Input

The first line of the input contains a single natural number N (1 ≤ N ≤ 30). The second line contains exactly N characters, which include digits and the symbol '*', representing free spaces. The line ends with a newline character.

Output

Output the number of N-digit Mirrorland numbers that can be formed by filling the free spaces with digits.

Examples

Note

The conditions of this problem should be interpreted literally.

To verify the answer for the first example, you can experiment with all possibilities on paper and hold them up to a mirror to identify which 3 options are valid.