Question

Сколькими способами из данного слова можно составить слово CAT?

Если индекс буквы C равен i, индекс буквы A равен j, а индекс буквы T равен k, то должно

выполняться условие i
Поскольку эти число может быть достаточно большим, выведите в качестве ответа остаток от

деления этого числа на 10000019

107 + 19

.

Формат входных данных:

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

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

A и хотя бы один символ T.

Формат выходных данных:

Выведите единственное целое число — остаток от деления на 10000019

107 + 19 количества

способов, которыми может сформировать слово CA

язык питон

Answer 1

def count_ways(s):

c_indices = [i for i in range(len(s)) if s[i] == 'C']

a_indices = [i for i in range(len(s)) if s[i] == 'A']

t_indices = [i for i in range(len(s)) if s[i] == 'T']

ways = 0

for c in c_indices:

for a in a_indices:

if a > c:

for t in t_indices:

if t > a:

ways += 1

return ways

def main():

s = input().strip()

ways = count_ways(s)

print(ways % (107 + 19))

if __name__ == '__main__':

main()