So Lippy

Author: mistertfy64

(The maximum score for this problem is 1010000 points.)

After Lia got fired from being an angel, she needed a friend to talk to. Thankfully, she met Iris, an old friend of hers.

Of course, when you see an old friend you haven't met for a while, you start to yap uselessly about what happened since last meeting that friend, and that is what happened to Lia, where she just kept talking and talking to Iris. So lippy and talkative!

She talked too much, both about the firing and how she got some secret information to spill to Iris, but she talked too much that she talked for over ten thousand characters!

Count the number of subsequences of the string in lip.txt that is the word LIP and denote it as S.

In other words, let S be the number of ways to remove some characters (possibly all or none, without changing the order of the remaining characters) in lip.txt, where the remaining string after the removal operations is exactly LIP.

For example, in the string LLIIP, there are 4 possible ways to get the word LIP:

• Remove characters 1 and 3. The remaining string, characters 2, 4, and 5, spell out LIP.
• Remove characters 1 and 4. The remaining string, characters 2, 3, and 5, spell out LIP.
• Remove characters 2 and 3. The remaining string, characters 1, 4, and 5, spell out LIP.
• Remove characters 2 and 4. The remaining string, characters 1, 3, and 5, spell out LIP.

and in the string LIPLI, there is 1 possible way to get the word LIP:

• Remove characters 4 and 5. The remaining string, characters 1, 2, and 3, spell out LIP.

Note that in the string LIPLI, removing characters 1 and 2 is not considered a way because the remaining string, characters 3, 4, and 5, spell out PLI instead of LIP, and neither is removing only character 5, since the remaining string, characters 1, 2, 3, 4, spell out LIPL instead of LIP.

The correct password is the remainder when S is divided by 1000000007. Do not include number separators (e.g., commas and/or dots) in your answer.

lip.txt (13.5kB .txt)

Correct Answers