The skillful thief finally confronted the uncle. Uncle, who is very money-loving, after seeing the bags of marbles and the number of marbles inside, realized that the thief had done a good job and tied uncle's hand. So the uncle decided to change the process of buying marbles from the thief.

In continuation of the previous question (marbles in the bag), we know that
n
A bag of marbles is arranged in a row on the table in front of the uncle and the thief. Place these bags of marbles in order with natural numbers of 1
n
We have numbered n, the bag
i
i in the row, no
i
i has The uncle and the thief realized that on each of these
n
n bag, a small English letter is written that identifies each previous owner of that bag. Uncle wants to select and buy a number of consecutive bags from the row; So that all those bags belong to a previous owner. (i.e. the letter written on all of them should be the same) These bags that the uncle chooses to buy must be a non-increasing interval; It means that you cannot choose a larger consecutive range of bags for purchase that includes the purchased range.

For example, if there are 5 bags on the table and the sequence of their "owners" is equal to aabcd, Uncle has 4 ways to choose the range to buy: the first two bags, the third bag, the fourth bag, or the fifth bag. If there are 3 bags on the table and the sequence of "owners" is equal to "aba", then uncle has 3 ways to choose the interval to buy: all intervals containing only one bag.

Uncle saw that he has a maximum of 100 choices for the purchase period; So, as a money-loving person, he began to bargain, "Now, you thief, you have come to arrange these bags in such a way that I have to choose between so many options! You have limited me, and you expect money?!"

After hearing this uncle's statement, the thief was horrified and started to argue that this was not done on purpose! The thief tried to convince the uncle by moving the bags so that the number of uncle's choices did not change.

For example, if the sequence of "owners" equals aabcd, the thief begins to explain, "If you look carefully, if I had arranged the bags so that the sequence would be aacbd, you still had 4 choices, great uncle. Aadbc too! baacd too!" and...

Uncle saw that the thief did not care about the story and continued to change the arrangement of the bags until he made all the positions for the "owners" sequence. So, because time is golden and uncle is a money lover, he asks you to take the input of the sequence of "owners" and tell him how many sequences of "owners" can be created by changing the order of the bags, in which uncle's choices are equal to the initial sequence.

Because this number may be very large and therefore uncle cannot read it, he asked you to declare the remainder of the answer to 1000003 (which is the number of keys to uncle's treasures).

input
The only input line contains a string of lowercase English letters representing the sequence of "owners" of the bags on the table.

The length of this sequence is max
500

000
It is 500,000.

Uncle is guaranteed to have a maximum of 100 selections for the shopping period.

output
In the only output line, print the remaining answer as 1000003.

Example
Sample entry 1
aabcd
Plain text
Sample output 1
24
Plain text
Sample entry 2
bzzooeerep
Plain text
Sample output 2
7200
Plain text
Sample entry 3
aba
Plain text
Sample output 3
1