Electrical switches

In Fuad's house, there are $m$ light bulbs and $n$ electrical switches. The light switches are numbered from $1$ to $n$, and the light bulbs from $1$ to $m$. Each switch can be connected to zero or more light bulbs. Each light bulb is connected to two switches.

When a switch is toggled, the light bulbs connected to that switch will turn off if they were on, and turn on if they were off. Currently, some light bulbs are on, and some are off.

Since Fuad wants to become an electrical engineer, he decided to play with the light bulbs. He can toggle each switch no more than once. Fuad wants to toggle several switches in a specific sequence to turn on all the light bulbs. Determine if this is possible. If possible, find out how many different ways this can be done. Any two methods are considered different if the sequence of switch toggles is different.

Since the number of ways can be large, find the remainder when dividing the answer by $(10^9+7)$.

Input

The first line contains two integers $n(2\le n\le 500)$ and $m(1\le m\le n\cdot (n-1)/2)$ — the number of switches and light bulbs respectively. The next $m$ lines describe the light bulbs. The $i$-th bulb is described by three integers $a_i,b_i(1\le a_i\ne b_i\le n,1\le i\le m)$ and $c_i(0\le c_i\le 1,1\le i\le m)$. It is known that the $i$-th bulb is connected to switches with numbers $a_i$ and $b_i(a_i\ne b_i)$. $c_i$ indicates the initial state of the bulb. If $c_i=1$, then the bulb is on. If $c_i=0$, then the bulb is off.

For any two switches, each of them is guaranteed to be connected to at most one light bulb.

Output

In the first line, output yay! if all light bulbs can be turned on. Otherwise, output meh. In the second line, indicate the number of ways to turn on all the light bulbs (if possible). Since the number of ways can be large, output its remainder when divided by $(10^9+7)$.

Examples

In the first example, all light bulbs can be turned on in one of three ways:

• do not toggle any electrical switches;

• toggle switch $1$ first, then toggle switch $2$;

• toggle switch $2$ first, then toggle switch $1$;

Scoring

This problem consists of $3$ subtasks. Points for each subtask are awarded only if all the tests for that subtask are passed successfully.

For each subtask in this problem, if you correctly determine whether it is possible to simply turn on the light bulbs in all tests for this subtask, you will receive $40$ of the points for that subtask.

1. ($10$ points): $h<9$;

2. ($20$ points): $h<18$;

3. ($70$ points): there are no additional constraints;