pk-and-lullness-of-his-string-2

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.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: