Statement is not available in English language
C. CAT
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кот Бенедикт недавно узнал, как выглядит слово кот на английском языке (cat, если вдруг вы не знаете).

Бенедикт дремлет, и ему снится сон. В этом сне он видит экран, на котором последовательно одна за другой появляются буквы, быстро сменяя друг друга. Каждая буква — это либо $$$C$$$, либо $$$A$$$, либо $$$T$$$.

Букв много, но ему нужно дотронуться лапкой сначала до какой-то из букв $$$C$$$, потом до какой-то из букв $$$A$$$, а затем — до какой-то из букв $$$T$$$. Когда ему это удаётся, буквы пропадают, а на экране показывают забавный короткий ролик про котов.

Ваша задача — определить, сколькими способами Бенедикт может сформировать слово $$$CAT$$$. Поскольку это число может быть достаточно большим, выведите в качестве ответа остаток от деления этого числа на $$$10000019$$$ $$$\left( 10^7 + 19 \right)$$$.

Входные данные

В первой строке содержится непустая последовательность, состоящая из символов $$$C$$$, $$$A$$$, $$$T$$$ (заглавных букв латинского алфавита), в том порядке, в котором они появляются на экране. Последовательность имеет длину не более $$$10^5$$$ символов.

Гарантируется, что последовательность содержит хотя бы один символ $$$C$$$, хотя бы один символ $$$A$$$ и хотя бы один символ $$$T$$$.

Выходные данные

Выведите единственное целое число — остаток от деления на $$$10000019$$$ $$$\left( 10^7 + 19 \right)$$$ количества способов, которыми кот может сформировать слово $$$CAT$$$.

Система оценки

В подзадачах с первой по четвёртую применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

В пятой подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

Почти для всех подзадач требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач. Более подробно разбиение на подзадачи показано в таблице ниже.

Ради краткости будем обозначать входную строку $$$s$$$, а её длину $$$|s|$$$.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
12 (до 10)$$$|s| \le 6$$$нетполная
22 (до 10)$$$|s| \le 1000$$$,нетполная
строка является соединением трёх
строк: одной строки только из
символов $$$C$$$, другой — только из
символов $$$A$$$ и третьей — только из
символов $$$T$$$, т.е. имеет вид
$$$C \ldots CA \ldots AT \ldots T$$$
32 (до 10)в строке содержится только одиннетполная
символ $$$A$$$, $$$|s| \le 10^5$$$
42 (до 20)$$$|s| \le 10^2$$$1, 2, 3полная
50 (50)$$$|s| \le 10^5$$$1, 2, 3, 4первая ошибка

Примеры
Входные данные
CACATT
Выходные данные
6
Входные данные
ACTCT
Выходные данные
0
Входные данные
ATCCATATTA
Выходные данные
10
Примечание

Поясним приведённые примеры.

Перенумеруем буквы в первом примере, начиная с $$$1$$$. Тогда слово $$$CAT$$$ можно сформировать следующими способами: $$$1 2 5$$$, $$$1 2 6$$$, $$$1 4 5$$$, $$$1 4 6$$$, $$$3 4 5$$$, $$$3 4 6$$$. Иных способов последовательно выбрать сначала $$$C$$$, потом $$$A$$$, потом $$$T$$$, не существует.

Во втором примере нет ни одного способа последовательно получить слово $$$CAT$$$.

Перенумеруем буквы в третьем примере (также начиная с $$$1$$$). Способы, которыми можно получить слово $$$CAT$$$, будут следующими: $$$3 5 6$$$, $$$4 5 6$$$, $$$3 5 8$$$, $$$4 5 8$$$, $$$3 5 9$$$, $$$4 5 9$$$, $$$3 7 8$$$, $$$4 7 8$$$, $$$3 7 9$$$, $$$4 7 9$$$. В отличие от первого примера не все буквы участвуют в образовании слова.

Также приведём пояснение про вычисления с остатком от деления.

Пусть есть числа $$$a$$$ и $$$b$$$, которые нужно сложить и сообщить остаток от деления их суммы на число $$$d$$$. Можно сделать это непосредственно: сначала вычислить $$$s = a + b$$$, а затем посчитать $$$s \mod d$$$, где mod обозначена операция взятия остатка от деления.

Однако можно поступить и по-другому: сначала вычислить $$$q = a \mod d$$$ и $$$p = b \mod d$$$, а потом уже посчитать $$$(p + q) \mod d$$$. Действительно, если $$$a$$$ представимо в виде $$$k_a \cdot d + q$$$, а $$$b$$$ — в виде $$$k_b \cdot d + p$$$, то их сумма запишется как $$$s = (k_a + k_b) \cdot d + (q + p)$$$. При вычислении остатка от деления $$$s$$$ на $$$d$$$ определять его значение будет только сумма $$$(q + p)$$$.

Хотя по отдельности $$$q \lt d$$$ и $$$p \lt d$$$, их сумма может быть больше $$$d$$$, поэтому результат вычисляется именно как $$$(p+q) \mod d$$$.

Такой подход позволяет поддерживать результат вычислений не превосходящим значения $$$2 \cdot (d - 1)$$$.

Аналогично можно показать, что остаток от деления произведения чисел $$$a$$$ и $$$b$$$ на число $$$d$$$ будет определяться произведением их остатков — $$$(p \cdot q) \mod d$$$.