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.

Source: codechef | Difficulty: EASY
Tags: Constructive algorithms

Mathematics

Ad-hoc


Solutions:
for t in range(int(input())):
	s = input()
	n = 1
	for i in range(len(s)):
		if i % 2 == 0:
			if s[i] == 'l':
				n = n * 2
			if s[i] == 'r':
				n = n * 2 + 2
		else:
			if s[i] == 'l':
				n = n * 2 - 1
			if s[i] == 'r':
				n = n * 2 + 1
	print(n % (10 ** 9 + 7))


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
		elif s[j] == 'l':
			ini -= 1
		else:
			ini += 1
		ini %= 10 ** 9 + 7
	print(ini % (10 ** 9 + 7))


n = int(input())
testCases = []
for i in range(n):
	testCases.append(input())
for case in testCases:
	ind = 1
	for j in case:
		if j == 'l':
			if ind % 2 == 0:
				ind = ind * 2 - 1
			else:
				ind = ind * 2
		elif j == 'r':
			if ind % 2 == 0:
				ind = ind * 2 + 1
			else:
				ind = ind * 2 + 2
	print(ind % (10 ** 9 + 7))


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
		elif 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())):
	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
		elif 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()
	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)


for _ in range(int(input())):
	S = input()
	ans = 1
	for i in range(len(S)):
		if i % 2 == 0:
			if S[i] == 'l':
				ans = 2 * ans
			elif S[i] == 'r':
				ans = 2 * ans + 2
		elif S[i] == 'l':
			ans = 2 * ans - 1
		elif S[i] == 'r':
			ans = 2 * ans + 1
		ans %= 2 * (10 ** 9 + 7)
	print(ans % (10 ** 9 + 7))


mod = 1000000007
t = int(input())
while t:
	s = input()
	k = len(s)
	i = 1
	j = 1
	while j <= k:
		if s[j - 1] == 'l' and j & 1:
			i = i * 2
		elif s[j - 1] == 'l' and (not j & 1):
			i = i * 2 - 1
		if s[j - 1] == 'r' and j & 1:
			i = (i + 1) * 2
		elif s[j - 1] == 'r' and (not j & 1):
			i = (1 + i) * 2 - 1
		j = j + 1
	i = i % mod
	print(i)
	t = t - 1


import sys
t = int(input())
for x in range(0, t):
	data = sys.stdin.readline().strip().split()
	data = data[0]
	ans = 1
	level = 1
	for i in range(0, data.__len__()):
		if level % 2 == 1:
			if data[i] == 'l':
				ans = ans * 2
			else:
				ans = ans * 2 + 2
		elif data[i] == 'l':
			ans = ans * 2 - 1
		else:
			ans = ans * 2 + 1
		level = level + 1
	ans = ans % (10 ** 9 + 7)
	print(ans)


t = int(input())
for _ in range(t):
	l = list(input())
	x = 1
	for i in range(len(l)):
		if i % 2 == 0:
			if l[i] == 'l':
				x = x * 2
			elif l[i] == 'r':
				x = x * 2 + 2
		elif l[i] == 'l':
			x = x * 2 - 1
		elif l[i] == 'r':
			x = x * 2 + 1
	print(x % 1000000007)


for i in range(int(input())):
	mod = 10 ** 9 + 7
	seq = input()
	level = 0
	st = 1
	for k in seq:
		level += 1
		if k == 'l':
			if level % 2 == 1:
				st = 2 * st
			else:
				st = 2 * st - 1
		elif k == 'r':
			if level % 2 == 1:
				st = 2 * st + 2
			else:
				st = 2 * st + 1
	print(st % mod)


def solve_for(path):
	odd = True
	p = pow(10, 9) + 7
	p = 1
	for c in path:
		if odd:
			odd = False
			if c == 'l':
				p = 2 * p
			elif c == 'r':
				p = 2 * p + 2
		else:
			odd = True
			if c == 'l':
				p = 2 * p - 1
			elif c == 'r':
				p = 2 * p + 1
	return p % (pow(10, 9) + 7)
T = int(input())
for i in range(T):
	ins = input()
	print(solve_for(ins))


for t in range(int(input())):
	s = input()
	count = 1
	ans = 1
	for i in range(len(s)):
		if s[i] == 'l':
			if count % 2 == 1:
				ans = ans * 2
			else:
				ans = ans * 2 - 1
		if s[i] == 'r':
			if count % 2 == 1:
				ans = ans * 2 + 2
			else:
				ans = ans * 2 + 1
		count += 1
		ans = ans % 1000000007
	print(ans)


def Chef_ltor(query):
	if not query:
		return -1
	level = 0
	last_node = 1
	for direction in query:
		if level % 2 == 0:
			if direction == 'l':
				last_node = last_node * 2 % 1000000007
			elif direction == 'r':
				last_node = (last_node * 2 + 2) % 1000000007
			else:
				level -= 1
		elif direction == 'l':
			last_node = (last_node * 2 - 1) % 1000000007
		elif direction == 'r':
			last_node = (last_node * 2 + 1) % 1000000007
		else:
			level -= 1
		level += 1
	return last_node % 1000000007
TestCase = int(input())
while TestCase:
	query = input()
	print(Chef_ltor(query))
	TestCase -= 1


for _ in range(int(input())):
	s = input().strip()
	(n, x) = (1, False)
	for i in s:
		n = 2 * n
		if x:
			n -= 1
		if i == 'r':
			n += 2
		x = not x
	mod = 10 ** 9 + 7
	print(n % mod)


t = input()
for c in range(0, int(t)):
	s = input().strip()
	(n, x) = (1, False)
	for i in s:
		n = 2 * n
		if x:
			n -= 1
		if i == 'r':
			n += 2
		x = not x
	mod = 10 ** 9 + 7
	print(n % mod)


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


T = int(input())
for x in range(0, T):
	s = input()
	l = len(s)
	n = 1
	for i in range(1, l + 1):
		if i % 2 == 1:
			if s[i - 1] == 'l':
				n = n * 2
			if s[i - 1] == 'r':
				n = n * 2 + 2
		elif i % 2 == 0:
			if s[i - 1] == 'l':
				n = n * 2 - 1
			elif s[i - 1] == 'r':
				n = n * 2 + 1
	print(n % (10 ** 9 + 7))


t = int(input())
for i in range(t):
	a = input()
	pos = 1
	for j in range(len(a)):
		if a[j] == 'l' and j % 2 == 0:
			pos = 2 * pos
		if a[j] == 'l' and j % 2 == 1:
			pos = 2 * pos - 1
		if a[j] == 'r' and j % 2 == 0:
			pos = 2 * pos + 2
		if a[j] == 'r' and j % 2 == 1:
			pos = 2 * pos + 1
	print(pos % 1000000007)


import sys

def main():
	b = []
	t = int(input())
	for i in range(0, t):
		s = input()
		ans = 1
		for i in range(0, len(s)):
			if i % 2:
				if s[i] == 'l':
					ans = ans * 2 - 1
				elif s[i] == 'r':
					ans = ans * 2 + 1
			elif s[i] == 'l':
				ans = ans * 2
			elif s[i] == 'r':
				ans = ans * 2 + 2
		print(ans % 1000000007)
main()


from sys import stdin
t = int(stdin.readline())
for i in range(0, t):
	s = list(stdin.readline().strip())
	l = 1
	r = 1
	rt = 1
	c = '\x00'
	flg = 1
	for c in s:
		if c == 'l':
			if flg > 0:
				l = rt * 2
			else:
				l = rt * 2 - 1
			flg = -flg
			rt = l
		else:
			if flg > 0:
				l = rt * 2
			else:
				l = rt * 2 - 1
			r = l + 2
			rt = r
			flg = -flg
	if c == 'l':
		print(l % (10 ** 9 + 7))
	else:
		print(r % (10 ** 9 + 7))


for _ in range(int(input())):
	l = input()
	n = 1
	count = 1
	for i in l:
		if i == 'l':
			if count % 2 == 1:
				n = n * 2
			else:
				n = n * 2 - 1
		if i == 'r':
			if count % 2 == 1:
				n = n * 2 + 2
			else:
				n = n * 2 + 1
		count += 1
	print(n % (10 ** 9 + 7))


x = int(input())
for i in range(x):
	put = input()
	curr = 1
	level = 1
	for z in put:
		if z == 'l':
			curr = curr * 2 + (level - 1)
		if z == 'r':
			curr = curr * 2 + 1 + level
		level = ~level + 2
	print(curr % (10 ** 9 + 7))


for T in range(int(input())):
	S = input()
	node = 1
	for i in S:
		if i == 'l':
			if node % 2 != 0:
				node = node * 2
			else:
				node = node * 2 - 1
		elif i == 'r':
			if node % 2 != 0:
				node = node * 2 + 2
			else:
				node = node * 2 + 1
	node = node % 1000000007
	print(node)


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)


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)

def alg(s):
	MOD = 10 ** 9 + 7
	v = 1
	cur_odd = True
	for path in s:
		v = v * 2 % MOD
		if cur_odd:
			if path == 'l':
				pass
			else:
				v += 2
		elif path == 'l':
			v -= 1
		else:
			v += 1
		cur_odd = not cur_odd
	return v % MOD

def main():
	data = sys.stdin
	nb = int(data.readline())
	for icase in range(nb):
		s = data.readline().strip()
		res = alg(s)
		print(res)
main()


for i in range(int(input())):
	current = 1
	strng = input()
	for j in range(len(strng)):
		level = j + 1
		if strng[j] == 'l':
			if level % 2 == 0:
				current = 2 * current - 1
			else:
				current = 2 * current
		if strng[j] == 'r':
			if level % 2 == 0:
				current = current * 2 + 1
			else:
				current = current * 2 + 2
	print(current % 1000000007)


t = input()
t = int(t)
while t > 0:
	s = input()
	e = len(s)
	e = int(e)
	n = 1
	for i in range(0, e):
		if s[i] == 'l' and i + 1 & 1:
			n = n * 2
		elif s[i] == 'l' and (i + 1) % 2 == 0:
			n = n * 2 - 1
		elif s[i] == 'r' and i + 1 & 1:
			n = (n + 1) * 2
		elif s[i] == 'r' and (i + 1) % 2 == 0:
			n = (n + 1) * 2 - 1
		n = n % 1000000007
	(print(int(n)), '\n')
	t = t - 1


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


t = int(input())
for i in range(t):
	s = input()
	j = 0
	sum = 1
	for i in s:
		if j % 2 == 0:
			if i == 'l':
				sum = 2 * sum
			elif i == 'r':
				sum = 2 * sum + 2
		elif i == 'l':
			sum = 2 * sum - 1
		elif i == 'r':
			sum = 2 * sum + 1
		j = j + 1
	print(sum % 1000000007)


for _ in range(int(input())):
	l = []
	s = str(input())
	mod = 10 ** 9 + 7
	for i in range(len(s)):
		l.append(s[i])
	x = 1
	count = 1
	for i in range(len(l)):
		if l[i] == 'l':
			if count % 2 != 0:
				x = 2 * x
			else:
				x = 2 * x - 1
		elif l[i] == 'r':
			if count % 2 != 0:
				x = 2 * x + 2
			else:
				x = 2 * x + 1
		count += 1
		x = x % mod
	print(x)


mod = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	S = input()
	level = 1
	i = 1
	for j in range(len(S)):
		if S[j] == 'l':
			if level % 2 == 0:
				i = i * 2 - 1
			else:
				i = i * 2
		if S[j] == 'r':
			if level % 2 == 0:
				i = i * 2 + 1
			else:
				i = i * 2 + 2
		level += 1
		i = i % mod
	print(i)


mod = int(1000000000.0 + 7)
for tc in range(int(input())):
	s = input().strip()
	node = 1
	for i in range(len(s)):
		node = node * 2
		if i & 1:
			node += mod - 1
		if s[i] == 'r':
			node += 2
		node %= mod
	print(node)


def something():
	tests = int(input())
	for test in range(tests):
		s = input()
		num = 1
		level = 1
		for char in s:
			if char == 'l':
				if level == 1:
					num *= 2
				else:
					num = num * 2 - 1
			elif char == 'r':
				if level == 1:
					num = num * 2 + 2
				else:
					num = num * 2 + 1
			level = 1 - level
		print(num % (pow(10, 9) + 7))
	return 0
something()


t = int(input())
for i in range(t):
	String = input()
	lvl = 1
	child = 1
	for j in range(len(String)):
		if String[j] == 'l':
			if lvl % 2 == 1:
				child *= 2
			else:
				child = child * 2 - 1
		if String[j] == 'r':
			if lvl % 2 == 1:
				child = child * 2 + 2
			else:
				child = child * 2 + 1
		lvl += 1
		child = child % 1000000007
	print(child)


for _ in range(int(input())):
	s = input()
	st = 1
	lvl = 1
	m = 1000000007
	for i in s:
		if lvl % 2 != 0:
			if i == 'l':
				st = st * 2 % m
			elif i == 'r':
				st = (st * 2 % m + 2) % m
		else:
			if i == 'l':
				st = (st * 2 % m - 1) % m
			if i == 'r':
				st = (st * 2 % m + 1) % m
		lvl += 1
	print(st)


b = []
test = input()
test = int(test)
while test > 0:
	n = 1
	a = input()
	for x in range(0, len(a)):
		if x % 2 == 0:
			if a[x] == 'l':
				n = n * 2
			if a[x] == 'r':
				n = 2 * n + 2
		else:
			if a[x] == 'l':
				n = 2 * n - 1
			if a[x] == 'r':
				n = 2 * n + 1
		n = n % 1000000007
		b.append(n)
	print(b.pop(), end='\n')
	b = []
	test = test - 1


T = int(input())
while T > 0:
	T = T - 1
	l = input()
	n = 1
	for j in range(len(l)):
		if l[j] == 'l':
			if j % 2 == 0:
				n = (n << 1) % 1000000007
			else:
				n = ((n << 1) - 1) % 1000000007
		if l[j] == 'r':
			if j % 2 == 0:
				n = ((n << 1) + 2) % 1000000007
			else:
				n = ((n << 1) + 1) % 1000000007
	print(n)


import math
n = int(input())
ans = True
for i in range(n):
	m = 1
	st = input()
	for j in range(1, 1 + len(st)):
		if j % 2 != 0:
			if st[j - 1] == 'l':
				m *= 2
			elif st[j - 1] == 'r':
				m = (m + 1) * 2
			else:
				ans = False
		elif st[j - 1] == 'l':
			m = 2 * m - 1
		elif st[j - 1] == 'r':
			m = 2 * m + 1
		else:
			ans = False
	m %= pow(10, 9) + 7
	print(m)


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


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
		elif i == 'l':
			ans = 2 * ans
		else:
			ans = 2 * ans + 2
		ans = ans % 1000000007
		level += 1
	print(ans)


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


import sys
T = int(sys.stdin.readline())
C = 10 ** 9 + 7

def func(inp):
	curr = -1
	if len(inp) == 1:
		if inp[0] == 'l':
			print(2)
		else:
			print(4)
	else:
		if inp[0] == 'l':
			curr = 2
		else:
			curr = 4
		for (index, item) in enumerate(inp):
			if index == 0:
				continue
			if (index + 1) % 2 == 0:
				if item == 'l':
					curr = 2 * curr - 1
				else:
					curr = 2 * curr - 1 + 2
			elif item == 'l':
				curr = 2 * curr
			else:
				curr = 2 * curr + 2
		if curr < C:
			print(curr)
		else:
			print(curr % C)
for _ in range(T):
	inp = str(sys.stdin.readline()).strip()
	func(inp)


class Node:

	def __init__(self, label):
		self._label = label

	def right_child(self):
		child_label = None
		if self._label % 2 == 0:
			child_label = self.get_label() * 2 + 1
		else:
			child_label = self.get_label() * 2 + 2
		return Node(child_label)

	def left_child(self):
		child_label = None
		if self._label % 2 == 0:
			child_label = self.get_label() * 2 - 1
		else:
			child_label = self.get_label() * 2
		return Node(child_label)

	def get_label(self):
		return self._label

class PathAnalyzer:

	def analyze_path_with_recursion(self, path: str):
		root_node = Node(1)
		target_node = self.find_node_with_recursion(root_node, path)
		return target_node.get_label()

	def find_node_with_recursion(self, parent_node: Node, remaining_path: str):
		next_node = remaining_path[0]
		if next_node == 'l':
			child_node = parent_node.left_child()
		elif next_node == 'r':
			child_node = parent_node.right_child()
		if len(remaining_path) == 1:
			return child_node
		else:
			return self.find_node_with_recursion(child_node, remaining_path[1:])

	def analyze_path(self, path: str):
		current_node = Node(1)
		for next_node in path:
			if next_node == 'l':
				child_node = current_node.left_child()
			elif next_node == 'r':
				child_node = current_node.right_child()
			current_node = child_node
		return current_node.get_label() % (10 ** 9 + 7)
test_number = int(input())
path_analyzer = PathAnalyzer()

def print_matrix_level(level):
	levels_info = [{'level': 1, 'max': 1, '#elem': 1}, {'level': 2, 'max': 4, '#elem': 2}]
	for new_level in range(3, level + 1):
		new_level_elements = 2 ** (new_level - 1)
		new_level_max = levels_info[new_level - 3]['max'] + new_level_elements * 2
		level_info = {'level': new_level, 'max': new_level_max, '#elem': new_level_elements}
		levels_info.append(level_info)
	print(levels_info[-1])
for test in range(test_number):
	test_path = input()
	test_result = path_analyzer.analyze_path(test_path)
	print(test_result)


import sys
a = input('').replace('\n', '').strip()
num_test_cases = 0
try:
	num_test_cases = int(a)
except ValueError:
	sys.exit()
for i in range(0, num_test_cases):
	a = input('').replace('\n', '').strip()
	node_number = 1
	is_odd_level = False
	for char in a:
		if is_odd_level == True:
			if ord(char) == ord('l'):
				node_number = node_number * 2 - 1
			else:
				node_number = node_number * 2 + 1
		elif ord(char) == ord('l'):
			node_number = node_number * 2
		else:
			node_number = node_number * 2 + 2
		is_odd_level = not is_odd_level
	print(node_number % (10 ** 9 + 7))


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


n = int(input())
for i in range(n):
	a = input()
	ans = 1
	for j in range(len(a)):
		if a[j] == 'l':
			ans = ans * 2 - j % 2
		elif a[j] == 'r':
			ans = ans * 2 + 2 - j % 2
	ans = ans % (10 ** 9 + 7)
	print(ans)


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


for __ in range(int(input())):
	a = input()
	rt = 1
	for i in range(len(a)):
		if i % 2 == 0:
			if a[i] == 'l':
				rt = 2 * rt
			elif a[i] == 'r':
				rt = 2 * rt + 2
		elif a[i] == 'l':
			rt = 2 * rt - 1
		elif a[i] == 'r':
			rt = 2 * rt + 1
	print(rt % (10 ** 9 + 7))


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


import math
for _ in range(int(input())):
	root = 1
	s = str(input())
	m = int(math.pow(10, 9) + 7)
	l = 1
	for i in s:
		if l % 2 == 0:
			if i == 'l':
				root = (2 * root % m - 1) % m
			elif i == 'r':
				root = (2 * root % m + 1) % m
		elif i == 'l':
			root = 2 * root % m
		elif i == 'r':
			root = (2 * root % m + 2) % m
		l += 1
	print(root)


def main():
	from sys import stdin, stdout
	for _ in range(int(stdin.readline())):
		g = 1
		s = stdin.readline().strip()
		for i in range(len(s)):
			if i & 1:
				if s[i] == 'r':
					g = (g << 1) + 1
				elif s[i] == 'l':
					g = (g << 1) - 1
			elif s[i] == 'r':
				g = (g << 1) + 2
			elif s[i] == 'l':
				g = g << 1
		stdout.write(str(g % 1000000007) + '\n')
main()


modulus = 1000000007
T = int(input())
for i in range(0, T):
	answer = 1
	inputStr = input()
	length = len(inputStr)
	for j in range(0, length):
		if (j + 1) % 2 == 1:
			if inputStr[j] == 'l':
				answer = answer * 2 % modulus
			elif inputStr[j] == 'r':
				answer = (answer * 2 + 2) % modulus
		if (j + 1) % 2 == 0:
			if inputStr[j] == 'l':
				answer = (answer * 2 - 1) % modulus
			elif inputStr[j] == 'r':
				answer = (answer * 2 + 1) % modulus
	print(answer)


import sys
MOD = 1000000007

def main():
	T = int(sys.stdin.readline().strip())
	for _ in range(T):
		S = str(sys.stdin.readline()).strip()
		node = 1
		for i in range(len(S)):
			if i + 1 & 1:
				if S[i] == 'l':
					node = (node << 1) % MOD
				else:
					node = ((node << 1) + 2) % MOD
			elif S[i] == 'l':
				node = ((node << 1) - 1) % MOD
			else:
				node = ((node << 1) + 1) % MOD
		print(node)
main()


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


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


t = int(input())
while t > 0:
	nn = 1
	ss = str(input()).strip()
	for i in range(1, len(ss) + 1):
		if i % 2 == 0:
			if ss[i - 1] == 'l':
				nn = nn * 2 - 1
			else:
				nn = nn * 2 + 1
		elif ss[i - 1] == 'l':
			nn = nn * 2
		else:
			nn = nn * 2 + 2
		nn = nn % 1000000007
	nn = nn % 1000000007
	print(str(nn))
	t = t - 1


for _ in range(int(input())):
	a = input()
	n = len(a) + 1
	tree = []
	odd = 1
	even = 2
	res = 1
	for i in range(len(a)):
		if i % 2 == 0:
			if a[i] == 'l':
				res = 2 * res
			elif a[i] == 'r':
				res = 2 * res + 2
		elif a[i] == 'l':
			res = 2 * res - 1
		elif a[i] == 'r':
			res = 2 * res + 1
		res %= 2 * (10 ** 9 + 7)
	print(res % (10 ** 9 + 7))


t = int(input())
modulo = 1000000000 + 7
while t > 0:
	string = input().rstrip()
	level = len(string)
	ans = 1
	for i in range(0, level):
		if i % 2 == 0:
			if string[i] == 'l':
				ans = 2 * ans
			else:
				ans = 2 * ans + 2
		elif string[i] == 'l':
			ans = 2 * ans - 1
		else:
			ans = 2 * ans + 1
		if ans > modulo:
			ans = ans % modulo
	print(ans % modulo)
	t -= 1