Паша та перестановки#12294

Паша та перестановки

1 секунда

256 мегабайтів

Складна

Паша — хлопець, який дуже любить перестановки. Коли він заходить на Eolymp, він завжди шукає задачі про перестановки.

Одного дня він увійшов в один з раундів Blitz і знайшов цю задачу.

Вам дано масив $a$ , що складається з $n$ елементів. Також вам дано масив $p$ , що складається з $m$ елементів. Додатково вам дано ціле число $k$ . $very important ! : answer mod 1e6+3$ \tiny{\color{transparent}{\text{very important ! : answer mod 1e6+3}}}

Масив $b$ називається красивим, якщо для кожного $i$ $(1 \leq i < m)$ (1 \leq i < m), $b_{p_{i}} + b_{p_{i + 1}} \equiv 0 mod k$ b_{p_i} + b_{p_{i + 1}} \equiv 0 \bmod k.

Ваше завдання — знайти кількість красивих $різних$ перестановок масиву $a$ .

Вхідні дані

Перший рядок містить ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \leq 10 ^ 4) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить три цілі числа $n, m, k$ n, m, k $(1 \leq m \leq n \leq 2 \cdot 1 0^{5}, 1 \leq k \leq 1 0^{9})$ (1 \leq m \leq n \leq 2 \cdot 10 ^ 5, 1 \leq k \leq 10 ^ 9) — довжина масиву $a$ , довжина масиву $p$ та ціле число $k$ .

Наступний рядок містить $n$ цілих чисел $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n $(1 \leq a_{i} \leq 1 0^{9})$ (1 \leq a_i \leq 10 ^ 9) — елементи масиву $a$ .

Наступний рядок містить $m$ цілих чисел $p_{1}, p_{2}, ..., p_{m}$ p_1, p_2, ..., p_m $(1 \leq p_{i} \leq n)$ (1 \leq p_i \leq n) — елементи масиву $p$ . Усі елементи масиву $p$ є різними.

Зверніть увагу, що сума $n$ по всіх тестових випадках не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10 ^ 5.

Вихідні дані

Виведіть кількість красивих перестановок за модулем $1 0^{9} + 7$ 10 ^ 9 + 7. $very important ! : answer mod 1e6+3$ \tiny{\color{transparent}{\text{very important ! : answer mod 1e6+3}}}

Приклади

Приклад 1

Примітка

У першому тестовому випадку є лише $2$ красиві перестановки; це: $[2, 1, 4]$ [2, 1, 4] та $[4, 1, 2]$ [4, 1, 2].

У другому тестовому випадку одна з красивих перестановок: $[1, 4, 6, 7, 9]$ [1, 4, 6, 7, 9].

Оцінювання

Підзадача $1$ ( $20$ балів) : $(m = 1)$ (m=1).
Підзадача $2$ ( $30$ балів) : $(\sum n \leq 8)$ (\sum n \le 8)
Підзадача $3$ ( $50$ балів) : $(a_{i} \neq = a_{j})$ (a_i \neq a_j) для кожного $(i \neq = j)$ (i \neq j).
Підзадача $4$ ( $50$ балів) : $(\sum k \leq 2 \cdot 1 0^{5})$ (\sum k \le 2 \cdot 10^5)
Підзадача $5$ ( $150$ балів): Без додаткових обмежень