There are ~N~ non-moving planets in the galaxy and can be represented as a 3D coordinate. Each planet is colonized by one and only one of the ~K~ alien colonies that exist in the galaxy. The tension between the colonies is high, so recently, the god of the galaxy decided to hold a meeting at the center of the galaxy ~(0, 0, 0)~. As a result, each colony must send one and only one alien representative to the meeting.

To get to the center of the galaxy, the aliens must fly from a planet of their colony and move axis-aligned and can only change directions at lattice points. Because the meeting is critical, every alien move that the alien takes must make him closer to the center of the galaxy. More formally, if the alien is at cell ~(x, y, z)~, he can only move to cell ~(a, b, c)~ if and only if ~|x| + |y| + |z| > |a| + |b| + |c|~. Also, because the tensions are so high, each alien can only visit planets that are only colonized by its colony.

As the god of the galaxy, you are wondering how many different ways are there to get each type to be represented at the meeting modulo ~10^9+7~. Two ways are different, if at least one of the paths taken by an alien is different, or if at least one alien is from another planet.

Input Specification

The first line will contain ~N~ ~(1 \le N \le 300)~ and ~K~ ~(1 \le K \le N)~ in this order.

Then, the next ~N~ lines will contain 4 integers ~x_i~, ~y_i~, ~z_i~ ~(0 \le |x_i|, |y_i|, |z_i| \le 10^5)~, and ~t_i~ ~(1 \le t_i \le K)~. They represent the x-coordinate, y-coordinate, z-coordinate, and which colony controls the planet, respectively.

There will not be a planet at ~(0, 0, 0)~ and no two different planets will have the same coordinate.

Output Specification

Print one integer, the number of ways modulo ~10^9+7~.

Subtasks

Subtask 1 [11%]

~N = 1~

~0 \le x_i, y_i, z_i \le 10^2~

Subtask 2 [23%]

~K = 1~

Subtask 3 [66%]

No additional constraints.

Sample Input 1

1 1
2 3 0 1

Sample Output 1

10

Sample Input 2

3 1
0 0 2 1
0 0 7 1
0 0 -1 1

Sample Output 2

3

Sample Input 3

2 2
1 1 3 1
1 0 2 2

Sample Output 3

42