Cho hai dãy \(a\) và \(b\) đều gồm \(n\) phần tử và số nguyên \(m\). Hãy tính \(\displaystyle \frac{a_1 \times a_2 \times \ldots \times a_n}{b_1 \times b_2 \times \ldots \times b_n} \ \% \ m\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 10^5, 2 \leq m \leq 10^9, m\) là số nguyên tố\()\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i < m)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(b_1, b_2, \ldots, b_n\) \((1 \leq b_i < m)\).
• Dữ liệu đảm bảo rằng tồn tại một dãy \(c\) là hoán vị của dãy \(b\) mà \(a_i\) chia hết cho \(c_i\) với mọi \(i \leq i \leq n\).

Output

• Một số nguyên duy nhất là đáp án của bài toán.

Example

5 11
6 7 8 9 10
1 2 3 4 5

10