A group of people is going for a fun trip to a city coordinated at \((1,\ 1)\). During their visit, a network started spreading all over the world. After knowing about the network, they decided to safely return to their home town coordinated at \((n,\ m)\). Among all the paths from \((1,\ 1)\) to \((n,\ m)\), some got in the contact with this network. They want to avoid networked paths and hence started calculating the total number of safe paths. Since it can take them a lot of time to find all the safe paths, so they have asked you to help.

You have been given a map in the form of a matrix of size \(n\times m\). Each coordinate represents a city on the map. You are required to find the total number of safe paths starting from city \((1,\ 1)\) and ending at city \((n,\ m)\). You are allowed to move either right or down in a single move, that is, if you are at city \((x,\ y)\), then you can go to either \((x+1,\ y)\) or \((x,\ y+1)\) in a single move. You are not allowed to move outside the map.

A path is networked if product of all the numbers in the path is divisible by \(X\).

Input format

Note: Since the input matrix can be very large, therefore you are given only \(k\) coordinate's values and remaining coordinates have values \(w\).

• The first line contains four space-separated integers \(n\ m\ k\ w\).
• The next \(k\) lines contain three space-separated integers \(x\ y\ v\) denoting the coordinate \((x,\ y)\) has value \(v\).

Output format

Print a single integer denoting the total number of safe paths modulo \(10^9+7\).

Constraints

\(1 \le n,\ m \le 10^6\\ 1 \le k \le 5000\\ n\times m > k\\ 1 \le v \le 10^{18}\\ 1 \le w \le 10^6\\ 1 \le x \le n\\ 1 \le y \le m\\ X = 100000007700000049\)