Sixpack

The glossy, fashionable National Gentlemen and Ladies Beer Magazine runs monthly contests aimed mainly at young IT experts, who are of course also the magazine's main subscribers. A contest is based on the so-called Sixpack puzzle, printed on the first page of the magazine over a stylish beer foam background. The puzzle consists of a rectangular grid with two rows and three or more columns. Some cells in the grid are empty, some contain a single decimal digit, and different cells may contain different digits. In extreme cases the grid may be empty or completely filled. Any three consecutive columns in the grid are called a sixpack, which is where the puzzle gets its name.

The grid comes with an integer K, which is an integral part of the puzzle.

The reader's task is to fill each empty cell in the grid with a single digit so that the sum of the values in each sixpack equals K. Different cells may contain different digits. The reader then sends their solution to the magazine's advisory board. The board keeps track of all the solutions it receives. If the reader's solution is the same as some solution the board received earlier, the reader wins no prize. If the reader's solution differs from every solution the board has received so far, the reader wins a package of real beer sixpacks from a quality beer brand. The number of sixpacks in the package equals the number of different puzzle solutions the board had immediately after receiving the reader's solution.

Two solutions are considered different if they differ in the contents of at least one cell at the same position in the grid.

A reader can send at most one solution. Any additional solution from the same reader is always dismissed. The board's secretary guarantees that the board never receives two or more solutions at the same moment.

Given a particular Sixpack puzzle, calculate the maximum number of beer sixpacks a magazine reader can win in the contest. The magazine is so popular that you can be sure the number of magazine readers is greater than the number of distinct solutions of the puzzle.

The input specifies one Sixpack puzzle. The first line contains three integers N (3 ≤ N ≤ 105), K (0 ≤ K ≤ 100), and M (0 ≤ M ≤ 2 · 105). N is the number of columns in the grid, K specifies the required sum in each sixpack, and M is the number of predefined values in the grid. Each of the following M lines contains three integers C (0 ≤ C ≤ N − 1), R (0 ≤ R ≤ 1), and V (0 ≤ V ≤ 9). C and R give the column and row of a cell in the grid, and V is the predefined value in that cell. Each cell's value is given at most once.

Output the maximum possible number of sixpacks a magazine reader can win. Print this number modulo 1 000 000 007.