Racing Results

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.

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.

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.

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