Chef has a nice complete binary tree in his garden. Complete means that each node has exactly two sons, so the tree is infinite. Yesterday he had enumerated the nodes of the tree in such a way: 
- Let's call the nodes' level a number of nodes that occur on the way to this node from the root, including this node. This way, only the root has the level equal to 1, while only its two sons has the level equal to 2.
- Then, let's take all the nodes with the odd level and enumerate them with consecutive odd numbers, starting from the smallest levels and the leftmost nodes, going to the rightmost nodes and the highest levels.
- Then, let's take all the nodes with the even level and enumerate them with consecutive even numbers, starting from the smallest levels and the leftmost nodes, going to the rightmost nodes and the highest levels.
- For the better understanding there is an example: 
1
/           \
2                   4
/   \                /       \
3       5           7        9
/ \      /  \          /  \       /  \
6  8 10 12      14 16   18 20 

Here you can see the visualization of the process. For example, in odd levels, the root was enumerated first, then, there were enumerated roots' left sons' sons and roots' right sons' sons.
You are given the string of symbols, let's call it S. Each symbol is either l or r. Naturally, this sequence denotes some path from the root, where l means going to the left son and r means going to the right son.
Please, help Chef to determine the number of the last node in this path.

-----Input-----
The first line contains single integer T number of test cases.
Each of next T lines contain a string S consisting only of the symbols l and r.

-----Output-----
Per each line output the number of the last node in the path, described by S, modulo 109+7.

-----Constraints-----
- 1 ≤ |T| ≤ 5
- 1 ≤ |S| ≤ 10^5
- Remember that the tree is infinite, so each path described by appropriate S is a correct one.

-----Example-----
Input:
4
lrl
rll
r
lllr
Output:
10
14
4
13

-----Explanation-----
See the example in the statement for better understanding the samples.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
MOD=10**9+7
for _ in range(int(input())):
    s=input()
    ind=1
    level=1
    for i in range(len(s)):
        if s[i]=='l':
            if level%2==1:
                ind=ind*2
            else:
                ind=ind*2-1
        if s[i]=='r':
            if level%2==1:
                ind=ind*2+2
            else:
                ind=ind*2+1
        level+=1
        ind%=MOD
    print(ind)




MOD = 10 ** 9 + 7
for _ in range(int(input())):
    s = input()
    ind = 1
    level = 1
    for i in range(len(s)):
        if s[i] == 'l':
            if level % 2 == 1:
                ind = ind * 2
            else:
                ind = ind * 2 - 1
        if s[i] == 'r':
            if level % 2 == 1:
                ind = ind * 2 + 2
            else:
                ind = ind * 2 + 1
        level += 1
        ind %= MOD
    print(ind)


mod = 1000000007
for _ in range(int(input())):
    string = list(input().strip())
    idx = 1
    lev = 1
    for i in (string):
        if i == 'l':
            if lev % 2 == 1:
                idx = (idx * 2)
            else:
                idx = (idx * 2 - 1)
        else:
            if lev % 2 == 1:
                idx = (idx * 2 + 2)
            else:
                idx = (idx * 2 + 1)
        lev += 1
        idx = idx % mod
    print(idx)

t = int(input())
for i in range(t):
    s = input().strip()

    level =1
    ans = 1
    for i in s:

        if(level%2==0):
            if(i=="l"):
                ans = 2*ans-1
            else:
                ans = 2*ans+1

        else:
            if(i=="l"):
                ans = 2*ans

            else:

                ans = 2*ans +2
        ans = ans%1000000007
        level +=1

    print(ans)
                


mod=1000000007
for _ in range(int(input())):
    s=input().strip()
    level=1
    ans=1
    for a in s:
        if level%2!=0:
            if a=="l":
                ans=2*ans
            else:
                ans=2*ans+2
        else:
            if a=="l":
                ans=2*ans-1
            else:
                ans=2*ans+1
        ans=ans%mod
        level+=1  


    print(ans)

mod=1000000007
for _ in range(int(input())):
    s=input().strip()
    level=1
    ans=1
    for a in s:
        if level%2!=0:
            if a=="l":
                ans=2*ans
            else:
                ans=2*ans+2
        else:
            if a=="l":
                ans=2*ans-1
            else:
                ans=2*ans+1
        ans=ans%mod
        level+=1  


    print(ans)

T=int(input())
for i in range(T):
	s=input().strip()
	ini=1
	for j in range(len(s)):
		ini*=2
		if j%2==0:			
			if(s[j]=='r'):
				ini+=2
		else:
			if(s[j]=='l'):
				ini-=1
			else:
				ini+=1
		ini%=(10**9+7)
	print(ini%(10**9+7))

t=int(input())
for i in range(t):
    s=input().strip()
    x=1
    a=1000000007
    for j in range(len(s)):
        if(s[j]=='l' and j%2==0):
            x=(x*2)%a
        elif(s[j]=='l' and j%2!=0):
            x=(x*2-1)%a
        elif(s[j]=='r' and j%2==0):
            x=(x*2+2)%a
        else:
            x=(x*2+1)%a
    print(x%a)