Cipher Lock

Time Limit: 2 Seconds
Memory Limit: 65536 KB

*CSBCLW* (the Company Sells the Best Cipher Lock in the World) has just invented a new cipher lock. The internal structure of the cipher lock looks like a `N`-regular polygon, and its vertices, are key points, while two attributes can be set on them. The first attribute on the vertices is can be represented by an integer ranging from 1 to `P`, and the second attribute is can be represented by an integer ranging from 1 to `Q`. Only if all the vertices meet the condition that every pairs of adjacent vertices have at least one attribute in common, the cipher would be legal.

Due to security reasons, there are exact 8 special constraints on the lock. Each constraint are described as a tuple with three integers (`X`, `U`, `V`). It means on the `X`-th vertex of the lock, the two attributes must be `U` and `V`. Under this limitation, *CSBCLW* wants to know how many different locks can be produced.

#### Input

There are multiple test cases (no more than 100). For each test case:

The first line contains three integers `N`, `P` and `Q` (1 <= `N`, `P`, `Q` <= 10 ^ 10).

Then followed by 8 lines. Each line contains three integers `X` (1 <= `X` <= N), `U` (1 <= `U` <= `P`) and `V` (1 <= `V` <= `Q`).

#### Output

For each test case, output the number of different locks module 1234567890.

#### Sample Input

16 2 2
1 1 1
3 1 2
5 1 1
7 2 1
9 2 2
11 1 1
13 2 1
15 1 2

#### Sample Output

256

Author:

**WANG, Xiajun**
Submit
Status