Banner

With a day to go until the cheerful parade in honour of Chairman Äčm's jubilee, your banner factory received a last-minute order! A very important order. You can vividly imagine your kids growing up in an orphanage if this banner is not ready on time. (Or perhaps that is just paranoia. As Chairman Äčm famously said: "Our country is blessed with large numbers, and astonishing coincidences.") Your factory has 26 machines, each specialised for rapidly sewing a unique uppercase letter onto fabric. The banner is a string of uppercase letters. At the beginning of the day, you arrange the 26 machines into a line. Any nonempty substring of this line may be sewn onto the banner. There are $26 \times 27 / 2 = 351$ nonempty substrings. Then the workers make the banner. Each hour, they start at the leftmost unsewn letter and sew the longest possible substring of the banner starting at that position. Each substring takes exactly one hour to sew, and only one substring may be sewn at a time. Figure B.1: One of the optimal permutations for Sample Input 2. For example, consider the permutation in Figure B.1. If the string to be sewn is HURRAHPATRIOT, the banner is completed in 6 hours: HUR in the first hour, R in the second, AH in the third, PA in the fourth, T in the fifth, and RIOT in the sixth. A permutation of the machines is optimal if no other permutation can finish the banner in fewer hours. How many permutations are optimal?

The input is a single line containing the string to be sewn onto the banner. The string uses only uppercase letters and has at least 1 and at most 35 characters.

Print the number of optimal permutations modulo each of Chairman Äčm's four favourite prime numbers: 1 000 000 007, 1 000 000 009, 1 000 000 021, and 1 000 000 033.