I love iiitb !

0

0 votes
Problem

Prof. X teaches algorithms at IIITB. In one his classes, he asks the students "How many of you love IIITB ?" . All hands go up. Then he continues "how many of you love Dynamic programming ?". All hands go up again. Prof. X smiles and displays some random text on the screen. He says "Count the number of 'I LOVE IIITB' subsequences in this text. Since this could be a large number, he asks the students to apply modulo ( (10 ^ 9) + 7 )

Input:

First line contains the number of testcases T . This is followed by T lines of input text.

Output:

T lines of the count of the number of subsequences of "I LOVE IIITB"

Constraints:

Input text will be in capital letters.

1 <= T <= 40

0 <= length of the input string <= 450

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?