I I U C   O N L I N E   C O N T E S T   2 0 0 8

Problem J: Digit Blocks

Input: standard input

Output: standard output

Often digit blocks are used to teach children formation of numbers. Block sets are available in the market which contains many blocks, each of which has the shape of a digit. Small or large numbers can be formed using them by placing them in a single row. Given the information of the available digit blocks, your job is to find out the total number of different hexadecimal numbers divisible by 5 that can be formed using those blocks. To save you from numbers with leading zeroes you can assume that none of the blocks will have shape of zero. The available blocks may have shapes of ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’,’9’, ‘A’, ‘B’, ‘C’, ‘D’, ‘E’ or ‘F’ which are actually digits of hexadecimal number system.  

Input

Input file contains at most 501 lines of inputs. Each line contains a string which contains only digits of hexadecimal number system (but will not contain zero). These digits denote the blocks that are available. For example if the string is “A1BBB5”, then you have two assume that total six blocks are available. Of them three blocks have shape of B, one block has shape of A, another block has shape of 1 and the last one has shape of 5. The string can be at most 16 characters long.

Input is terminated by a line containing a single ‘#’.

Output

For each line of input produce one line of output. This line contains a decimal integer number which denotes the value N. Here N is the number of hexadecimal multiples of 5 that can be formed using the given digits. Note that you can use some or all of the given digits to form number. You can safely assume that N will fit in a 64 bit signed integer.

Sample Input

Output for Sample Input

A1BBB5

B

#

4

0

Problem setter: Shahriar Manzoor

Special thanks: Derek Kisman