Distinct Moves

Given a string s consisting only of l/r, choose a subsequence of it. Starting from x, l decreases the position by 1 and r increases it by 1. The start, the position after every step, and the end must all lie within the bounded number line 0..n, and the walk must end at y. Count distinct character sequences: the same character sequence obtained from different indices counts only once. Return the count modulo 1000000007. Reflecting off a boundary, staying put instead of crossing it, 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 the end is outside 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 any other out-of-domain endpoint gives 0. The bounded domain comes from the Flexport original; the empty subsequence follows the usual definition of a subsequence, supported by the explicit deletion definition in the Meesho version of the same problem, and non-emptiness is not additionally required.

样例 1

输入：

rrlrr
6 1 4

输出：

2

样例 2

输入：

rr
2 0 1

输出：

1

样例 3

输入：

rl
1 0 0

输出：

2

样例说明

The first example keeps the Flexport original input rrlrr,6,1,4 but corrects the original answer 3 to 2: only rrr and rrlrr work, as proven by enumerating all 32 index subsets; the local-machine image is inaccessible and is not used as evidence. The last two examples are derived by this site: rr from 0 to 1 counts r only once; rl from 0 back to 0 counts the empty string and rl. Flexport itself gives the complete numeric constraints.