Задано дерево. Для кожної вершини дерева є набір елементів, які можна поміщати в цю вершину. Кожен елемент має вагу – деяке ціле число. Для кожного ребра дерева визначено відношення між вершинами, а саме, відомо, у якій з двох вершин повинен бути елемент з меншою вагою. Потрібно визначити кількість різних способів розташування у вершинах дерева по одному елементу такого, щоб для всіх ребер виконувались відношення. Різні елементи з набору однієї вершини можуть мати однакову вагу.

Вхідні дані

У першому рядку задано кількість вершин 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.