Racing Results

Time limit2sMemory limit128 MB

Summary

Count how many full car rankings are consistent with given pairwise 'beat' results, essentially counting linear extensions of a partial order mod 1,000,003.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Graph, Topological sort
Solved: No attempts yet

Problem

An entrant wants to predict all possible final race rankings from earlier race results. If car A has beaten car B before, assume that A must finish ahead of B in this race as well.

These assumptions may still leave more than one final ranking.

Suppose 4 cars participate, and the only known earlier results are that 1 beat 2 and 1 beat 3. Then the possible rankings are 4123, 4132, 1423, 1432, 1243, 1342, 1234, and 1324, for a total of 8.

Given the number of cars and the known earlier results, compute how many current race results are possible.

Input

The first line contains the number of cars N participating in this race. N is a positive integer no greater than 30.

The second line contains the number of known earlier race results M. M is an integer between 0 and 15, inclusive.

Each of the next M lines contains one earlier result in the form A B. This means car A always beats car B. The cars are numbered from 1 through N.

Output

Print the number of possible race results modulo 1,000,003.

If the earlier results contradict each other so that no ranking is possible, print 0.

Hint

With only the constraint 2 3, the possible race results are 123, 213, and 231.

Examples4

Example 1
Input
```
3
1
2 3
```
Expected output
```
3
```
Example 2
Input
```
4
2
1 2
1 3
```
Expected output
```
8
```
Example 3
Input
```
10
3
2 3
3 4
4 2
```
Expected output
```
0
```
Example 4
Input
```
30
0
```
Expected output
```
90317
```