레이싱 결과

어떤 참가자는 이전 레이스 결과를 바탕으로 이번 레이스의 가능한 최종 순위를 예측하려고 한다. 이전 경기에서 자동차 A가 자동차 B를 이긴 기록이 있으면, 이번 레이스에서도 A는 항상 B보다 앞선다고 가정한다.

이 가정만으로 최종 순위가 하나로 정해지지 않을 수 있다.

가령 이번 레이스에 자동차 4대가 참가하고, 알려진 이전 결과가 1이 2를 이겼고 1이 3을 이겼다는 것뿐이라면 가능한 순위는 4123, 4132, 1423, 1432, 1243, 1342, 1234, 1324의 8가지이다.

자동차의 수와 알려진 이전 경기 결과가 주어질 때, 가능한 현재 경기 결과의 수를 구하라.

첫째 줄에 이번 레이스에 참가하는 자동차 수 N이 주어진다. N은 30 이하의 자연수이다.

둘째 줄에 알려진 이전 경기 결과의 수 M이 주어진다. M은 0 이상 15 이하의 정수이다.

다음 M개 줄에는 이전 경기 결과가 A B 형식으로 주어진다. 이는 자동차 A가 자동차 B를 항상 이긴다는 뜻이다. 자동차 번호는 1부터 N까지 하나씩 붙어 있다.

가능한 경기 결과의 수를 1,000,003으로 나눈 나머지를 출력한다.

이전 경기 결과끼리 모순되어 가능한 순위를 정할 수 없다면 0을 출력한다.

제약이 2 3 하나뿐인 경우 가능한 경기 결과는 123, 213, 231이다.