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

Вам дан ориентированный граф, состоящий из $$$n$$$ вершин и $$$m$$$ рёбер. Каждой вершине $$$v$$$ соответствует некоторое положительное число $$$a_v$$$. Посчитайте количество различных простых путей$$$^{\text{∗}}$$$, состоящих хотя бы из двух вершин, таких, что последовательность чисел, записанных в вершинах на пути, образует обобщённую последовательность Фибоначчи.

В этой задаче мы будем считать, что последовательность чисел $$$x_0, x_1, \ldots, x_k$$$ образует обобщённую последовательность Фибоначчи, если:

  • $$$x_0, x_1$$$ — произвольные натуральные числа.
  • $$$x_i = x_{i - 2} + x_{i - 1}$$$ для всех $$$2 \le i \le k$$$.

Обратите внимание, что обобщённая последовательность Фибоначчи состоит как минимум из двух чисел.

Так как ответ может быть большим, выведите его остаток от деления на $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Простой путь в ориентированном графе — это последовательность вершин $$$v_1, v_2, \ldots, v_k$$$ такая, что каждая вершина графа встречается в пути не более одного раза и существует ориентированное ребро из $$$v_i$$$ в $$$v_{i+1}$$$ для всех $$$i \lt k$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два числа $$$n$$$, $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — количество вершин и количество рёбер в графе соответственно.

Вторая строка каждого набора входных данных содержит $$$n$$$ натуральных чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — числа, записанные в вершинах.

В следующих $$$m$$$ строках содержатся рёбра графа, каждое ребро задаётся двумя натуральными числами $$$v, u$$$ ($$$1 \le v, u \le n$$$, $$$u \neq v$$$), обозначающее ориентированное ребро из $$$v$$$ в $$$u$$$. Гарантируется, что в графе нет кратных рёбер.

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите количество путей, образующих обобщённую последовательность Фибоначчи, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4
4 4
3 4 3 6
1 2
1 3
2 4
3 4
4 6
1 1 1 2
1 2
2 3
3 1
1 4
2 4
3 4
8 11
2 4 2 6 8 10 18 26
1 2
2 3
3 1
4 3
2 4
3 5
5 6
4 6
6 7
7 5
5 8
2 2
10 10
1 2
2 1
Выходные данные
5
9
24
2
Примечание

Объяснение первого набора тестовых данных примера (вне скобок указан номер вершины, в скобках — число, записанное в вершине):

В этом наборе есть 5 обобщённых путей Фибоначчи: ($$$1, 2$$$), ($$$1, 3$$$), ($$$2, 4$$$), ($$$3, 4$$$), ($$$1,3,4$$$). Например, для пути ($$$1,3,4$$$) последовательность чисел, записанная на вершинах данного пути, равна: [$$$3,3,6$$$]. Как легко видеть, третье число последовательности является суммой двух предыдущих.

Объяснение второго набора тестовых данных примера:

В этом наборе есть 9 обобщённых путей Фибоначчи: ($$$1, 2$$$), ($$$1, 4$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$3, 1$$$), ($$$3, 4$$$), ($$$1, 2, 4$$$), ($$$2, 3, 4$$$), ($$$3, 1, 4$$$). Обратите внимание, что для пути ($$$1, 2, 3$$$) последовательность чисел, записанная на вершинах данного пути, равна: [$$$1,1,1$$$] и она не является обобщённой последовательностью Фибоначчи.