407933: GYM102944 J Jackson

Little Jackson is learning to spell! Recently he learned the word "michigan". He is very excited to find all the occurrences of "michigan" on the street, even if they are spread out and hidden in other words. For example, 'michigan' occurs twice in 'momichigan' (because you can eliminate the first two letters, or the 2nd and 3rd letters). You can check that it occurs three times in 'mimichiganmi'. One day, Little Jackson sees an electric newsboard on the street. There are N characters on this board, but due to bugs the screen sometimes goes blank just as he finishes his count.Little Jackson screams, "how can I check the michigans when the world is changing so fast?"

Take pity on Little Jackson. Write a program that checks Little Jackson's answer before the screen goes blank.

The first line contains a string $$$S$$$ ($$$1\le |S| \le 10^6$$$), consisting of characters 'a'-'z' and underscore '_' (which represents the whitespaces).

Output a number that represents the occurrence of subsequences that equals to "michigan". Since these numbers may be large, all you need to do is modulo the answer by $$$10^9+7$$$.

momichigan

2

mimichiganmi

3

magician

0