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