ZCC’s English is so poor that his teacher GPS forced him to memorize words. In order to examine ZCC, GPS created a software. This software works as follow. A user inputs a string S which only consists of uppercase into this software, then the software calculates the score which string S has by using its strange methods.Initially the software stores n different words and the initial score is 1. The length of S is L. The chars of string S is labeled from 1 to L(left to right), and S[i] represent the i-th char of S.
// Prime[k] means the k-th prime number, such as Prime[1]=2, Prime[2]=3 ,Prime[8]=19.
Input >> S
Score = 1
For i = 1 to L do
For k=1 to n do
If S[j..i] equals to Word[k]
Score = Score * Prime[k] * ( i * 2 - j + 1 )
Output << Score
The pseudocode above shows when input S what score we can get.
If n=2,L=3,Word[1]=”AB”,Word[2]=”BB” then
Score[ABB] = 1 * ( 2 * 2 - 1 + 1 ) * Prime[1] * ( 3 * 2 - 2 + 1 ) * Prime[2],
Score[CBA] = 1,
Score[CAB] = 1 * ( 3 * 2 - 2 + 1 ) * Prime[1];
ZCC has found a BUG which can help him to input strings into the software as much as he can. And the score he gets in the end is the sum of the score he gets in each input.ZCC wants to know the score he will get in the end, if he input all the different strings into the software. That is to say if the length of string is L, he can input 26^L strings in all. The answer can be very large, so what ZCC actually want is the ans Mod 5047621.