You are playing Imperishable Night.
After overcoming numerous hardships, you have finally arrived before Kaguya-hime and answered her five difficult problems.
"If you want to clear the game, you still need to solve this sixth problem," is the response that awaits you:
"I have a rooted binary tree, but I have forgotten what it originally looked like. I only know that it has $n$ leaves, each leaf has an aesthetic value of $1$, and every non-leaf node has exactly two children. I also remember $k$ pieces of information: for any non-leaf node, if the number of leaves in its left subtree is $s_i$, then its aesthetic value is $v_i$. If none of the $k$ pieces of information are satisfied, its aesthetic value is $A$. The aesthetic value of the binary tree is the product of the aesthetic values of all its nodes. Now, please tell me the sum of the aesthetic values of all possible binary trees."
It is time to face this final challenge.
The answer may be very large; you only need to output the result modulo $10^9 + 7$.
Input
The first line contains three integers $n, k, A$. The next $k$ lines each contain two integers, representing $s_i$ and $v_i$.
Output
Output a single line containing one integer, the result modulo $10^9 + 7$.
Examples
Input 1
5 1 1 2 2
Output 1
25
Input 2
6 2 1 2 3 4 5
Output 2
268
Constraints
This problem uses subtask-based grading.
For all data, $1 \le n \le 10^6$, $0 \le k \le 10$, $1 \le s_i < n$, $0 \le v_i, A < 10^9 + 7$, and it is guaranteed that for all $i \neq j$, $s_i \neq s_j$.
- Subtask 1 (20 pts): $n \le 10^3$
- Subtask 2 (10 pts): $k = 0$
- Subtask 3 (40 pts): $n \le 5 \times 10^4$
- Subtask 4 (30 pts): No additional constraints