Задача F. Фантастическое чёрно-красное дерево

Автор:Завгороднев А.А., Бадерик М.М.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Существует фантастическое черное-красное дерево - граф, который представляет из себя дерево (связный граф без циклов), в котором каждая вершина покрашена в один из двух цветов - красный или черный.

У вас есть не менее замечательная строка s, состоящая из K символов ‘r' и 'b’. Ваша задача - выяснить сколько существует путей по дереву, таких, что если выписать цвета вершин, по которым вы прошлись, то получится строка s.

Путь - последовательность вершин, которая ведет из одной вершины в другую и проходит по ребрам графа. Одна вершина встречается в пути не более одного раза.

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

В первой строке целое число N- количество вершин в графе.

Далее строка g состоящая из N символов ‘r' и 'b’, описывающая цвета вершин дерева.

Далее строка s, состоящая из K символов ‘r' и 'b’.

В следующих строках два целых числа - ai и bi - начало и конец ребра.

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

Одно целое число - количество различных путей.

Ограничения

2 ≤ K ≤ N ≤ 104

Примеры тестов

Стандартный вход Стандартный выход
1
5
brbrr
rbr
1 3
4 3
3 5
2 3
6
2
5
brrbr
rb
1 2
1 5
3 4
5 4
4

0.072s 0.009s 13