Distinct Moves

Given a string s containing only l/r, choose a subsequence of it. Starting from x, l decreases the position by 1 and r increases it by 1; the start, every intermediate position, and the end must all lie on the finite number line 0..n, and the walk must end at y. Count distinct character sequences; the same character sequence coming from different indices counts only once. Return the count modulo 1000000007. Reflecting, staying put when out of bounds, or leaving the domain and coming back are not allowed.

输入格式

The first line contains s, and the second line contains n x y. Full original ranges: 1≤|s|≤1000, s contains only l/r, 0≤n,x,y≤2500. The original does not guarantee x,y≤n, and this site keeps such inputs: if the start or end is not in 0..n, there is no valid path and the answer is 0.

输出格式

Output an integer in 0..1000000006. All characters may be deleted, so when x=y is valid, the empty subsequence contributes 1; for n=0,x=y=0 the answer is 1, and for any other out-of-domain endpoint the answer is 0. This interpretation follows the original's finite number line and deletion of zero or more elements, and does not additionally require a non-empty subsequence.

样例 1

输入：

rr
2 0 1

输出：

1

样例 2

输入：

lr
1 0 0

输出：

1

样例 3

输入：

rl
1 0 0

输出：

2

样例说明

All three public examples were derived by this site. For rr from 0 to 1, the string r counts only once, not as two index choices; for lr from 0 back to 0, lr goes out of bounds, so only the empty string is valid and the answer is 1; for rl from 0 back to 0, both the empty string and rl are valid, so the answer is 2.