triangulation triangulation triangulation

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

Today, I meet a difficult problem.
You are given three ints $n$, $x$, $y$. We have a regular n-gon: a convex polygon with $n$ sides, in which all sides have the same length and all internal angles are equal. We want to draw $n-3$ non-intersecting diagonals in some way. Once we do that, we will have the polygon divided into exactly $n-2$ triangles. We want to produce a situation in which one of these $n-2$ triangles has a $strictly$ larger area than each of the remaining $n-3$ triangles.
The vertices of the polygon are labeled $1$ through $n$ in clockwise order. Two sets of diagonals are different if one of them contains a diagonal that is not exist in the other one. Count all sets of $n-3$ non-intersecting diagonals that produce an arrangement with the above property. Output the number modulo $x$ multiple the number modulo $y$.
I can't solve it. Can you help me?
For example , the number of the first case is $(0\% 5)*(0\% 6)=0$,the number of the second case is $(5\% 6)*(5\% 7)=25$.

Input

First line contains an integer $T$ ($T \leq 2$), the number of test cases.
For each test case, there are three numbers $n, x, y$ in a line separated by blanks ($3 \leq n \leq 400, 1 \leq x, y \leq 10^9$).

Output

For each test case, print a single number in a line which is described above.

Sample Input

2 4 5 6 5 6 7

Sample Output

0 25

Hint

liuyiding

Source

2017 ACM/ICPC Asia Regional Shenyang Online

提交代码