题目描述
PK is presented a String S by daisy duck on his birthday.The length of this string is LEN.
Being an expert in measuring LULLness of string he wants to show of his
skills to impress daisy duck.The LULLness of a string is the number of such sub-sequences of a string which are GOOD strings.
A GOOD string is an odd length string.It's length is n(n ≥ 3),and it has a unique property, the middle most character of the string is 'u'
and all other characters are 'l'.So if length n=5,GOOD string is "llull".
Input:
the first line consists the input t(1 ≤ t ≤ 10),t is the number of testcases.
Each test case consists two inputs:
The string S having length LEN(1 ≤ LEN ≤ 100000)
The length of the string 'n' to be searched in S,(1 ≤ n ≤ S-1),n is odd.
Output:
Print the LULLNESS of the string modulo 10^9+7(1000000007),as the output might overflow.
P.S. : Subsequence of a string : http://en.wikipedia.org/wiki/Subsequence
SAMPLE INPUT
2
lul 3
ullullu 5
SAMPLE OUTPUT
1
1
Explanation
In the first test case there is only one GOOD string "lul" in the string S
In the second test case also the only GOOD string is "llull".
P.S. : Both the test cases are having Continuous good strings.
A sub sequence need not necessarily be continuous.
输入格式
见题面
输出格式
见题面
样例输入
10
uuuululllluuullluullulululuullllllllullllullluulluulululluluululllluuuuuullluulllluluulllulllllllluluullluulllluulluulullllulllluuuululullluuullluulluulllulllulluuuuuulluuulllluluuuluullllluluuuuulluluulululllllllulllululullllllllullllluluullllulululluuluuuulllluullulllulluuuululuululluullulluluuluuuluuuulululluluulllllluululuuullllluluulululllllluuululuullulllulullluluululuululuululuullulluululuululuuuullllullluuuluuullulllulululuuuluuuuluulululuullullllluulllullullluuuulullluuluulllluluuulllllllulullluuuuuulullulluulllullullululluuuulllllllllluluuuulllullullluuuuluullullululuuuuululllululllullulluulullulululluululluuulluuluulllluuululullluuulllluuluuullluuuuluuluulluuuuulluuulluuuuluuuulluuuullluulllluuullllluuululluluuuuulullllluulluluululuulullulluuullulllulluuuuuuuullulullllluuuluuuluuluuluuuuluuuuuuuuuulllllluluuulllllluluuulllululuuullllluluuluuuuuuullluluulllllllluuullullluuullullluuuuuuuulllluluuuuuuluullllllullluululuulluuluuulululullulluullluulluulluuuuuluullluuuululluluullu
985
luluuluullluuuulullluuuuullluulllluuuuuuuuululluuulllulululllullullullulullullululullllluuuullllllullullluulluululuuuluuululuuluuululuuluuluuuluuuuullluuluululluululluuuuluuulllulllllllulllllluuuullulluuullllllluuulluuulllluuullluulullllullullullllluululllulluuullullluluuuuuluullululuullluuluulllullluuuuluuuuuluululuuuluuulullluuuuuulllullululuullulluulllululuullulllllluuullllulullullulluulllluullullluulluluulluullullluluuuluullluullulllullulllllllluuullullluuullluuuluullllulllllulluluuuuuluuuulluluuullllluuulllullllluluuullulllluluuuuuuulllllllluuuuullulullluulluuuulllluullluullluuuullllllululluuuuuuuuulllluuuuluuuuuuullluuulluuululluuuulluuululluululuulullullluullluulluuuuulllllluluuuuullluulllluuululllululuulluullllulluulluululluuuulluluuuulllulluuuuluuululuuulluuullullllllllullluluuuuuuluuululuuuluuuullulullluullluluululluluuuuuulluululuuuuulluullululuuulllululululllluuuulllllllulullulluluuuulululluuluulllullullluuululuuuulllulluullulllullullullluuulluuuluuullluuluuuuluuluuuuulluuu
309
luuulullulluuulluuululuuluullulllluulllllulllluululuullllullullullllulluululuuulluululullllllllllluullllululllllllullllululuuuulullullululuululuulullulululluulllulullululluuluullullulluuluullllluullllululuuluulllululuullllluuuullullullluluulullulllulluuuuulluuullluuuluulullulluuulllulllluulluuluuluuuululllluuullluuuuluulluuuluuuluuuluuulululuuuuluuuuulullluluulluuuulllullluuuuuluullluluuuluulullululllullluullluluuulululullllluuululuulululuululluuullulllluluuuluuuuulllullllululuuuuuululuuluululuulluuluululuuullluuluuuulllllululllullullulllulllluuuuluuuluululuuulluuuululuuuullulluulluuulululluluuluuuuluuuuuuuluuuluullllllluuuluullulluuuluullluuluulululullluuulluluuuuuuullluuuuuuluuuluuululllluuuuluuululuuuuuuuululluulllluuulululuulllulluulluuluulllluuuuuuuuuuuuuulluuuullululllullllulluluuluulullullllulululluuluuuuuuuululuuullluuuulullulllulllllluuuululuuluulllululuulluulluululluuuluullllulllullulluululluluulululllullllluluulluulluuululuulululluulluuuuulullululuulullluuuuululuuluuluulluuu
981
uluulllulllllullluuuluuulullululluuulllluuulluluuuuullluululluluuuuullllllulllllululluluuulllluulllluluuuuuluuullluullululllullluulluuluuuullluuuluuulluulluuuuuuullullluluullullulluulllluluuluuluuuluuuulluluululluluuulululuulullllullullluuuluuullluuluulllluullululllluuuulluullllululllululululuuuuuuulluullluluulullullulluulullullllullllulllllululllululuuuuulllllluulllluuluuullluuuuluuuuullllulllulullluluuullllllllululululluluulluuuuuuuulllluuullluulluluuluulluulululuullululuuuullluululuuluululullulluulluluulullluuuluuluululuulllluuuuulululuuluullulluulluuuulululluuululuulllluluuuluuluulluuullllulllullulllullluluuuulllllulllllluuuuululuuuluululluululuululuulluluuuululullllllllullllulllllululllllllullulluulluluululuuullulullulluululllulllluullulullulllululuuuulullullluluuluululuulluululllluuluululllluulluululluuulullllulllullluluuullluluuullululllluuuuluulullluuulluluuullulllluuluuulluuluulllululullullluuuulluululluulluuluulluuuuuuullluuuuluuululuulluuuullullluuuuuluullluuululluuluullllul
149
lulllluulluluululululuuulluuulllluuuuuuuuuluuuuluululuullulllllulluuuullulululululuuluuluuluullluullllullluulluluuuuuluullluluuululululuuluuuuuululuuulluuluulululluluulluuluuuluuululluuuuuuluuululllulluluululululluullluluulululluuuuullluuuulllluuuuuuuululuuuuullllluulllulullulllullulllulluulluuulllluluuululuululuuulullululluluuuluulullllllllluuuluuluuuuluuuluulluulluululullulluluulululluluuulluulllullllllluluuulululllluuuuuuluuuuluulullllulllllluluulllluuuluuuluuluuluuuuuuululuuuluuululuuuluuluullllulullllllluululuululluullluullululullllllllulluluululuuuullllululllullllluluuululuuulullluuluulluuuluuululululluuluuluullulululullllllluulluuluululluluuuuuullluullulllluulluluuulluuulluuluuuuuuuulllluuuluulluullllllullluulluuuuluuuuuluuulluuluulllllulluulluuululullulluululululululluuuluuulluuullluulululuuluulllluulluuuuuluuuulllluuuuullluuuulllluluuluuulululluululuululluulllulluuuuulllulllllluullullluluuluuuluuuulullululllluullullluululuuullluullluuuuuululllulluuululuuullllluuulluulluuluullu
393
uulluluuluuuluuuuluuuuluuululuuuulluuulluluuuluuluuuululullluuluuluuulluluulllullluuuuuuuuuululuuuuullluuuullluullllluuulllululuulluuuuuulluuulllulllluuuulllllululuuulullllulluuuuuullulllululuuluuullluuuullullululululluullulluluuluullllllulluluuuuluuluuululluuullllululllllullllluulllulluulullulllllluuluululullluuuuuuulluuuullullluuuuluuululluuullluululullluluuuuululuulululuulllululuuluulullllulllluuuuluululluuuululluullullulululululuulluululuululuullluluullluullullulluulululuulluuluullulululuullluuuulllullulllluulullululllluulluluuluuuuulllululuululuuulllluullllululuuuulllluullluuuluuuluulluulullululululuulullluullllulululluluuuululullllllllulluullluluulluluululluulllllllluuuulllluluuululluluuuuuuuuuuulluuulullullluulluuuluuullllluuuluululllulluulululluluuluuuuluulllululuuluuullllluullullulllluullullluluullllululluuullululuuulllllululullullllluuuuuuuuuuuluuuuuuuullluluuuuullulullullllllllululuulluuululluuulluuuuuuullllulluullllllllllulululluullullllullullullulllulluuullullluuulluuluulu
689
uluululllluuulllullllullullullluullullllllluulluulluluuuuuuuuuuuuuulluuuuululllullululluuuuuullluuuuullulululllulllllllllulllllullullllllllllllullllllluluuulluluuuuuuuulllllluuuuluulluululuullluulululllullulllluuululluluullululluuullululullluuluuuulullullulluluuuuluulluulluullulllllulllllllluuuullulluluululuullllululullluululuulululuululuulululuuluulluuluuluullllluluulluluuulluuuuluululuuulululullullluulululluuuulluluuulllulllluuuuuululuuuullulllluullluuulluuuulllulullllulluuluulululuuullluuululuullllulluulllullluluuuuluulllllllluuluullluuullluuuuulullluluulullulululuulluululuuluullululuuluullllluuuluuluuuuuululululuuuuululullululullulluullluulluuuuulululullullullluululuuuluuluulluulululullluuluululuuuluuululllululluuluuullllulululluuuluuulluluulllluulllluluuluuluuuuuuuuululluuluuuluuullllululuuluulllllulululllulluulullluuuuuuluulllulllllulululluuuuuulluuulluuuulluulluulullulluulullululllluuulllluluuuluulluuuuulluuulllllulululuuuuulluuuulllulluulullllululuulluuluuuuluulluluulluuuuuuuuu
457
llluuululuuulluuluulllululululluuululuulluuululuuuulluuluulluluuuulluluulllllullluullluulluuuuullllulllulllllllluuluuullluuuulululllluuuullllllluuululluulluuuluululuuululllluluuullulllllluuuluuuluuluuuullululluuulluuullllullllllululullulllluuuluululluululuuulllluuulllluulluululluullluluuululuuuuuulluuuulllulluulullluuuululluuuululuuluulululuuulluuuuullluulluluulluulluullluluuuulllluuluuuuulluulluuluullluullulullullululuuuuululuuluuulluuullllllllllulluuululululluluuuuuulllullluuuuuuuuulluullluullllulululullluuluullluuuuululuulllululuuululluluuluuuuullluullllllluuuulluluulllulluuluulluuullullluulllluuluuuluuuuuullluuuulullullllulllllulllululllllullluluuuulluuluuluuulululluullullululululluulllllluuluululluuuulllllluuuuullluuuulllluuluuluuuulullluuuuuluululuuluuuuuuuluuuulluluulluuullluuuuluuluuluuuuluuuuulluuuuuuluuuuluululullluluullluuluullluluululluulllullllluuulluuluuluuuulululllllluuullululullllululuululullululullululullluulullluuluullulluuuuullulluuulluulullulluuuuulluuuulullulullluu
205
ulllluuullllluluuuullluuluullllluuuululllluluuuluulllllululluulluuluuuuululluuuulllullllluuululuuuuuullululullllluuuuuuulllululuuululullluuuuullluuuluulullluuulululllluuuulullllluulluulluulullluuuuuluulullluullululllluuullullluluuulluuuluuuuullullluululllllllululuuuulullulululluululuululluuuullluuullluululluuulllllluluullululuuuullllluuuuluulululullllullulullulullullllululluulluluuullllluluulluluulllluluulluuuulluulluuuluuuuuluuluullluuulullullllllluuuluuululluuulullulluuuuluuuuuuuululuuuuululullllulluluulluuulullululllluuulluuullulllllulllllluullluuulllullllluuululluluuluuuuuuuuluuluuuullulullllllluuuuuulllluuuuuuulullllulllullllululuuullluluuuuuuuululllullllluulluuuuulluluuulluluullulluuuuluululululluullluuuululllllllulluuulluluullllulllllllulullulullululluululuuullulluluuululuuululluluulllullulluuluulluluuuluuuuuuulullullullluuulluuuuuuullulululululuuuullullllulluuuullluuluuuuuullullllluuullllullulluluuuuululluluulluulullluuluuululluluuluuuuuullululuulllllllluluuuuuluuuullluuuuuuull
943
uuullluuulllulululuuluuluuuluululuuulullluuuullllullululuuuulullllluuuuululllululluullluuluuuuuuuluuuuuuluuulululuullluluuuuuluullllluulullulullllulluulluuulllulllllllllluululluullllulllulllllllululuuuluullulluluuuuulllululuuullllluuuuuuulululullluuulululullllluuuuuulluuuullluuuuluullluluuuullluuuluuuulullluuuulllluuuuululuullullllllluulllluluuulluulullululullulllllulullluluuulllllllluluuuulluuluuuulluluuuullulllllluluuululluluulluuuuluullulllulluuuuluulllullllulullluuuullluulullululluuulululluululuuullllulllululluuuluulluuuulluuuuuululullullllullllluuuuuuluuuuuuuuululllllluuulluuuuluulullullullluuluuuuuuuuullllululuululluuluululllulululluuuuluulullullllllllllluulluululllulluluuuluuuluuluuulllluuuulluullluuulllulululuuuuuluuuuulllluuuuluulllluuulluuuuuuuuuuuluuuuullulluuuuuuuluuluulluulllullululuuuuuulluululululuululuuuuuullullllululuuuullllullllullllllulllllulllllluuuullulululuuuulululululuuulluuululluuulllullulluuluulullulluluullluluuluuuuulluulllllulluuululuuuluuuuuuuululuuululllluu
129
样例输出
0
926314520
0
83576956
98458268
0
632408153
795887652
0
37978261