By XI Maratona de Programação IME-USP, 2007 Brazil
Canada is a very cold country. During eight months every year temperatures make virtually impossible for the streets to be occupied by intelligent life, leaving only cold-hardy creatures such as elk, bears, and Canadians (just kidding). During these long winter months families seek fun in front of their fireplaces (or, for the most courageous, around the fire). The Smith family, from Banff, invented the game we describe below.
The game begins with a children's drawing a diagram with states (represented by dots) connected by transitions (arrows connecting the states). Each transition has an associated letter and one number. We make several trips this diagram, starting from a start state walking through their transitions and ending in a final state . A walk form a word (obtained from the concatenation of the letters of the transitions covered) and has a cost (which is given by the product of the numbers of these transitions).
As an example, consider the diagram below.
Image 1: Diagram
All tours start in the P state and end in the Q state. The tour that follows the transitions (P, 1A), (P, 1A), (P, 1B) and ends in state Q form the word AAB concatenating the letters of each transition has cost 1 (product of the numbers of these transitions).
The tour that follows the transitions (P, 1A), (P, 1A), (P, 1B), (Q, 2B) and ends in the state Q generates the word AABB and has cost 2.
The game invented by father Smith was as follows. After drawing a diagram like this, one of the family members spoke a word, and others should find out the total cost of all tours on the diagram that form the given word such that it starts in state P and ends in state Q. For the example in the diagram above, if Mr. Smith asked the word ABA the answer should be 2.
The input consists of several words (the diagram is always the one in the figure). Each case is given by a line containing a word. A word is a sequence of letters [A, B] with a maximum of 60 letters. The input ends with end of file (EOF).
For each case, you should print a handle K, where K is the number of the current case. On the next line print the sum of costs. After each case print a blank line.
|Sample Input||Sample Output|