Дано дерево. Для каждой вершины дерева есть набор элементов, которые можно помещать в данную вершину. Каждый элемент имеет вес - некоторое целое число. Для каждого ребра дерева определено отношение между вершинами, а именно, известно, в какой из двух вершин должен быть элемент с меньшим весом. Требуется определить количество различных способов выбрать в вершинах дерева по одному элементу, чтобы все отношения на ребрах соблюдались. Разные элементы из набора одной вершины могут иметь одинаковый вес.

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

В первой строке дано количество вершин n (1 ≤ n ≤ 1000) в дереве. Далее следуют n строк, в i-ой строке дан список допустимых элементов в вершине i. Строка начинается с целого числа k (1 ≤ k ≤ 1000) - количества элементов. Далее следуют k целых чисел wj (1 ≤ wj ≤ 109) - веса элементов.

В каждой из следующих n - 1 строке записаны два различных целых числа a и b (1 ≤ a, b ≤ n), которые означают, что в дереве есть ребро между вершинами a и b, и в вершине a должен быть размещен элемент меньшего веса, чем в вершине b.

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

Вывести количество способов по модулю 1000000007.