Counting Possible Strings

President K once had a string (S) of length (N) consisting only of lowercase letters. Unfortunately, he forgot it. However, he remembers a peculiar property about (S) obtained from an old dictionary of misspellings he once saw.

For (1 \le i \le N), let (T_i) be the string obtained by removing the (i)th character from (S) (i.e. concatenating the prefix and suffix). He recalls that for every given pair ((A_j, B_j)) ((1 \le j \le M)), the following condition holds: [ T_{A_j} \le T_{B_j} ] where the lexicographical comparison (\le) means that either (T_{A_j} = T_{B_j}) or (T_{A_j}) is lexicographically smaller than (T_{B_j}).

It can be shown that for any two indices, the condition (T_i \le T_j) imposes a local restriction on adjacent characters in (S). In particular, one may prove that:

• If (i < j), then (T_i \le T_j) is equivalent to (s_{i} \ge s_{i+1}).
• If (i > j), then (T_i \le T_j) is equivalent to (s_{j} \le s_{j+1}).

Thus, for each pair ((A, B)):

• If (A < B), the condition forces (s_{A} \ge s_{A+1}).
• If (A > B), the condition forces (s_{B} \le s_{B+1}).

If both types of constraints affect the same adjacent pair (i.e. one forces (s_i \ge s_{i+1}) and another forces (s_i \le s_{i+1})), then it forces (s_i = s_{i+1}).

Your task is: Given (N) and (M) followed by (M) pairs of indices, count the number of possible strings (S) (of length (N) with lowercase letters) that satisfy all the conditions. Since the answer might be large, output it modulo (10^9+7).

It is guaranteed that (1 \le N \le 10^5) and (0 \le M \le N-1). Each of the following (M) lines contains two integers (A_j) and (B_j) ((1 \le A_j, B_j \le N, A_j \neq B_j)).

inputFormat

The first line contains two integers (N) and (M). Each of the next (M) lines contains two integers (A_j) and (B_j), representing a constraint that (T_{A_j} \le T_{B_j}).

outputFormat

Output a single integer: the number of possible strings (S) modulo (10^9+7).

sample

2 1
1 2

351