ColoringBalls

There are N white balls arranged in a row, numbered 1,2,..,N from left to right. AtCoDeer the deer is thinking of painting some of these balls red and blue, while leaving some of them white.

You are given a string s of length K. AtCoDeer performs the following operation for each i from 1 through K in order:

• The i-th operation: Choose a contiguous segment of balls (possibly empty), and paint these balls red if the i-th character in s is r; paint them blue if the character is b.

Here, if a ball which is already painted is again painted, the color of the ball will be overwritten. However, due to the properties of dyes, it is not possible to paint a white, unpainted ball directly in blue. That is, when the i-th character in s is b, the chosen segment must not contain a white ball.

After all the operations, how many different sequences of colors of the balls are possible? Since the count can be large, find it modulo 10^9+7.

Constraints

• 1 ≤ N ≤ 70
• 1 ≤ K ≤ 70
• |s| = K
• s consists of r and b.
• N and K are integers.

Input

Input is given from Standard Input in the following format:

N K s

Output

Print the number of the different possible sequences of colors of the balls after all the operations, modulo 10^9+7.

Examples

Input

2 2 rb

Output

9

Input

5 2 br

Output

16

Input

7 4 rbrb

Output

1569

Input

70 70 bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

Output

841634130

inputFormat

Input

Input is given from Standard Input in the following format:

N K s

outputFormat

Output

Print the number of the different possible sequences of colors of the balls after all the operations, modulo 10^9+7.

Examples

Input

2 2 rb

Output

9

Input

5 2 br

Output

16

Input

7 4 rbrb

Output

1569

Input

70 70 bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

Output

841634130

样例

70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

841634130