Орехус нашел строку \(s\), состоящую из латинских букв нижнего регистра. Орехус любознательный парень, поэтому ему стал интересен следующий вопрос: сколько существует строго возрастающих последовательностей \(p_1, p_2, \ldots, p_k\) таких, что:
- Для каждого \(i\) (\(1 \leq i \leq k\)), \(s_{p_i} =\) 'a'.
- Для каждого \(i\) (\(1 \leq i < k\)), существует \(j\), что \(p_i < j < p_{i + 1}\) и \(s_j =\) 'b'.
Удовлетворите любопытство Орехуса, или он расстроится.
Это число должно быть посчитано по модулю \(10^9 + 7\).
Выходные данные
В единственной строке выведите ответ — число искомых последовательностей \(p_1, p_2, \ldots, p_k\) по модулю \(10^9 + 7\).
Примечание
В первом примере \(5\) допустимых последовательностей. \([1]\), \([4]\), \([5]\), \([1, 4]\), \([1, 5]\).
Во втором примере \(4\) допустимых последовательности. \([2]\), \([3]\), \([4]\), \([5]\).
В третьем примере \(3\) допустимых последовательности. \([1]\), \([3]\), \([4]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abbaa
|
5
|
|
2
|
baaaa
|
4
|
|
3
|
agaa
|
3
|