На острове Герн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.
Выходные данные
Единственное целое число, количество подходящих комбинаций монет, которые могут быть у Бесси, по модулю 1000000007 (109 + 7).
Примечание
Для первого примера, следующие три комбинации в целом дают 17 центов и удовлетворяют данным условиям: {0 монет типа 1, 1 монета типа 2, 3 монеты типа 3, 2 монеты типа 4}, {0, 0, 6, 1}, {2, 0, 3, 1}.
Других комбинаций нет. Обратите внимание, что несмотря на то, что 4 встречается как в bi, так и в ci, условия задачи все равно удовлетворяются, потому что все bi различны и все ci различны по отдельности.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2 17
3 1 2 5
4 2
3 4
|
3
|
|
2
|
3 2 6
3 1 1
1 2
2 3
|
0
|
|
3
|
3 2 10
1 2 3
1 2
2 1
|
0
|