지금 나는 작은 토너먼트에서 내가 제일 좋아하는 팀이 우승할 확률이 얼마나 될지 알고 싶어합니다.

토너먼트에는 딱 네 팀이 출전했습니다. 모든 팀이 딱 한 번씩 경기를 치루면 총 6게임이 진행되고 토너먼트가 종료됩니다. 모든 게임은 어느 한 팀이 이기거나 무승부로 끝납니다. 게임이 무승부로 끝나지 않으면 승리한 팀이 3점, 진 팀은 0점을 얻고, 무승부로 끝나면 두 팀이 1점씩 얻습니다.

내가 응원하는 팀은 반드시 토너먼트 종료 시 반드시 모든 다른 팀보다 많은 점수를 가지고 있어야합니다. (공동 1등이란 타협은 할 수 없습니다)

아직 토너먼트가 끝나진 않았지만 나는 이미 진행된 모든 게임의 결과를 알고 있습니다. 나는 남은 경기의 결과에 따라서 어떻게 점수가 분배될 지 모든 경우의 수를 알아내 내가 응원하는 팀이 우승할 수 있는 방법이 총 몇 개가 되는지 알고 싶어 합니다.

입력

• 첫 번째 줄에 내가 응원하는 팀의 번호 T (1 ≤ T ≤ 4) 가 입력됩니다.
• 두 번째 줄에 이미 끝난 게임의 수 G (0 ≤ G ≤ 5) 가 입력됩니다.
• 다음 G 줄에 팀 번호 A, B, 두 팀의 점수 Sa, Sb (1 ≤ A < B ≤ 4, Sa, Sb ≥ 0) 가 공백으로 구분돼 입력됩니다. A가 이긴 게임이면 Sa > Sb, B가 이긴 게임이면 Sa < Sb, 무승부인 게임이면 Sa = Sb입니다.

출력

입출력 예

입력

3
3
1 3 7 5
3 4 0 8
2 4 2 2

출력

0

입력

3
4
1 3 5 7
3 4 8 0
2 4 2 2
1 2 5 5

출력

9

출처:CEMC (CCC 2013 Stage 1)
번역:ladown21