Даны две последовательности цветных камней. Цвет каждого камня либо красный, либо зеленый, либо синий. Также даны две строки, s и t. Символ номер i (1-индексация) строки s представляет цвет камня номер i в первой последовательности. Аналогично, символ номер i (1-индексация) строки t представляет цвет i-ого камня во второй последовательности. Если символ — «R», «G», или «B», то цвет соответствующего камня будет красный, зелёный или синий, соответственно.
Изначально Белка Лисска стоит на первом камне в первой последовательности, а кот Вася стоит на первом камне второй последовательности. Вы можете выполнить следующие инструкции ноль или больше раз.
Каждая из инструкций может быть одного из трех типов: «RED», «GREEN», или «BLUE». После инструкции c, животные, которые стоят на камне цвета c, перепрыгнут на камень вперед. Например, если применить инструкцию «RED», то животные, стоящие на красных камнях, прыгнут на камень вперед. Вам не разрешается выполнять инструкции, выводящие некоторых животных за пределы последовательности. Другими словами, если некоторое животное стоит на последнем камне, вы не можете выполнить инструкцию с цветом этого камня.
Пара позиций (позиция Лисски, позиция Васи) называется состоянием. Состояние называется достижимым, если это состояние достижимо при выполнении инструкций ноль или больше раз от исходного состояния (1, 1). Вычислите количество различных достижимых состояний.
Выходные данные
Выведите в единственной строке количество различных достижимых состояний.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел в С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом примере достижимых состояний пять: (1, 1), (2, 2), (2, 3), (3, 2), и (3, 3). Например, состояние (3, 3) достижимое, потому что если выполнить инструкции «RED», «GREEN», и «BLUE» в данном порядке из изначального состояния, то состояние будет (3, 3). Картинка ниже показывает, как в таком случае работают инструкции.
