C. Проблемы с монетками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На острове Гернcи существует n различных типов монеток. Для каждого i (1 ≤ i ≤ n), монетка типа i стоит ai центов. Возможно, что ai = aj для некоторых i и j (i ≠ j).

У Бесси есть небольшой набор таких монеток, который в сумме стоит t центов. Она назвала Джесси q пар целых чисел. Для каждого i (1 ≤ i ≤ q), пара bi, ci говорит Джесси, что у Бесси есть строго большее количество монеток типа bi, чем монеток типа ci. Так случилось, что все bi различны и все ci различны.

Помогите Джесси найти количество возможных комбинаций монеток, которые могут быть у Бессии. Две комбинации считаются различными, если есть некоторое i (1 ≤ i ≤ n), такое, что количество монет Бесси типа i различно в этих двух комбинациях. Так как ответ может быть достаточно большим, выведите его остаток от деления на 1000000007 (109 + 7).

Если нет комбинаций монеток, которые в сумме стоили бы t и удовлетворяли условиям Бесси, выведите 0.

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

Первая строка содержит три целых числа через пробел, n, q и t (1 ≤ n ≤ 300; 0 ≤ q ≤ n; 1 ≤ t ≤ 105). Вторая строка содержит n целых чисел через пробел, a1, a2, ..., an (1 ≤ ai ≤ 105). Следующие q строк содержат по два различных целых числа через пробел, bi и ci (1 ≤ bi, ci ≤ n; bi ≠ ci).

Гарантируется, что все bi различны и что все ci различны.

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

Единственное целое число, количество подходящих комбинаций монет, которые могут быть у Бесси, по модулю 1000000007 (109 + 7).

Примеры
Входные данные
4 2 17
3 1 2 5
4 2
3 4
Выходные данные
3
Входные данные
3 2 6
3 1 1
1 2
2 3
Выходные данные
0
Входные данные
3 2 10
1 2 3
1 2
2 1
Выходные данные
0
Примечание

Для первого примера, следующие три комбинации в целом дают 17 центов и удовлетворяют данным условиям: {0 монет типа 1, 1 монета типа 2, 3 монеты типа 3, 2 монеты типа 4}, {0, 0, 6, 1}, {2, 0, 3, 1}.

Других комбинаций нет. Обратите внимание, что несмотря на то, что 4 встречается как в bi, так и в ci, условия задачи все равно удовлетворяются, потому что все bi различны и все ci различны по отдельности.