Little N is a girl who loves things that trend upwards, as this often means good things are happening!

Because of this hobby, for a permutation $q_1, q_2, \dots, q_n$ of $1 \sim n$, Little N also likes to study its rising positions. Specifically, she defines the set of all rising positions in the permutation $q$ as $S(q) = \{1 \le i < n \mid q_i < q_{i+1}\}$.

Rising is a lucky thing, but how lucky it is is hard to quantify. So, Little N decided to assign a weight to each position in the permutation to quantify the "luck value." Specifically, she provided a sequence of non-negative integers $w_1, w_2, \dots, w_{n-1}$, and defined the luck value of the permutation $q$ as $f(q) = \prod_{i \in S(q)} w_i$. In particular, if $S(q) = \emptyset$, then $f(q) = 1$.

Little C is a good friend of Little N. One day, Little C gave her a lucky permutation $p_1, p_2, \dots, p_n$. However, due to various accidents, some elements in the permutation were lost, and the values at these missing positions became $0$.

After receiving the gift, Little N was not sad about the incompleteness of the permutation, because she was surprised to find that all non-missing elements in the permutation are still monotonically increasing, i.e., they form a monotonically increasing subsequence from left to right.

Little N immediately felt like the happiest girl in the world. At the same time, she was also curious about how lucky the original permutation sent by Little C was. Therefore, she wants to calculate the sum of the luck values $f(q)$ for all permutations $q$ that match $p$. A permutation $q$ matches $p$ if and only if: for all $1 \le i \le n$, either $p_i = 0$ or $q_i = p_i$.

Your task is to help Little N calculate the sum of the luck values $f(q)$ for all permutations $q$ that match $p$, modulo $m$.

Implementation Details

You do not need to, and should not, implement the main function. You must ensure that your submitted program includes the header file ascend.h, i.e., add the following code at the beginning of your program:

#include "ascend.h"

You need to implement the following function in your submitted source file ascend.cpp:

int ascend(int c, int n, int m, std::vector<int> p, std::vector<int> w);

• $c, n$ represent the test case number and the length of the permutation, respectively. $c = 0$ indicates that the test case is a sample.
• $p$ represents Little C's permutation after some positions were lost. For $0 \le i < n$, $p_i$ represents the value at the $(i+1)$-th position of the permutation after the loss.
• $w$ represents Little N's weight sequence. For $0 \le i < n - 1$, $w_i$ represents the weight of the $(i+1)$-th position.
• The function needs to return the sum of the luck values $f(q)$ for all permutations $q$ that match $p$, modulo $m$.
• For each test case, this function will be called exactly $t$ times by the interactor.

Examples

Input 1

0 1
3 6
0 2 0
2 3

Output 1

1

Note 1

There are two permutations $q$ that match $p$: 1. $q = [1, 2, 3]$, $S(q) = \{1, 2\}$, $f(q) = w_1 \times w_2 = 2 \times 3 = 6$; 2. $q = [3, 2, 1]$, $S(q) = \emptyset$, $f(q) = 1$. Therefore, the sum of the luck values of all permutations matching $p$ is $6 + 1 = 7$, and the result modulo $m = 6$ is $1$.

Constraints

For all test data, we have: $1 \le t \le 5$; $2 \le n \le 500$, $2 \le m \le 10^9$; For all $1 \le i \le n$, $0 \le p_i \le n$; All non-zero elements in the sequence $p$ form a monotonically increasing subsequence; * For all $1 \le i \le n - 1$, $0 \le w_i < m$.

Special Property A: For all $1 \le i \le n$, $p_i = 0$. Special Property B: $m \ge 5 \times 10^8$ and $m$ is a prime number.