만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

가위바위보 전략

시간 제한1초메모리 제한1024 MB

요약
N명의 참가자와 M개의 경기에서 참가자 명단과 승자가 주어질 때, 고정 손 또는 주기적 가위바위보 패턴 전략 배정 중 모든 결과와 모순되지 않는 경우의 수를 10^9+7로 나눈 나머지를 구한다.
난이도

어려움10점 중 8점

유형
구현, 완전 탐색, 수학
정답자
아직 제출이 없습니다

문제

UNIST 가위바위보 협회 회장인 윤이는 UNIST 학생들을 대상으로 가위바위보 대회를 열어 NN명의 참가자를 모았다. 대회는 총 MM번의 경기로 이루어진다. 각 경기에서는 두 명 또는 세 명의 참가자가 동시에 가위, 바위, 보 중 하나를 낸다. 그러면 다음 규칙에 따라 각 경기의 승자가 정해진다.

  • 바위는 가위를 이기고, 가위는 보를 이기며, 보는 바위를 이긴다.
  • 모두 같은 손 모양을 내면 경기는 무승부다.
  • 가위, 바위, 보가 모두 나오면 경기는 무승부다.
  • 무승부가 아니면 이기는 손 모양을 낸 사람이 모두 승자가 된다.

각 UNIST 학생은 이 대회를 위해 다음 전략 중 하나를 준비했다.

  • 항상 같은 손 모양만 낸다.
  • 가위, 바위, 보를 임의의 순서로 한 번씩 낸다. 이 패턴을 자신이 참가하는 매 세 경기마다 반복한다.

윤이는 서류가 많아서 대회를 직접 보지 못했다. 대신 윤이에게는 참가자 명단과 각 경기의 승자가 적힌 문서가 있다. 윤이는 학생들이 어떤 전략을 썼을지 궁금해졌다. 모든 학생의 가능한 전략 조합의 수를 109+710^9+7로 나눈 나머지를 구하라.

입력

첫째 줄에 두 정수 NN과 MM이 주어진다. (3≤N≤300,1≤M≤300)(3 \leq N \leq 300, 1 \leq M \leq 300) NN은 대회 참가자의 수, MM은 경기의 수다.

다음 MM개 줄에는 MM번의 경기에 대한 설명이 시간 순서대로 주어진다. 각 경기는 다음과 같이 주어진다.

  • 참가자의 수 aa가 주어진다. (a=2 또는 a=3)(a=2\text{ 또는 }a=3)
  • 참가자 번호 p_1,⋯ ,p_ap\_1, \cdots, p\_a가 주어진다. 이들은 11부터 NN까지의 서로 다른 정수다.
  • 구분자 /가 주어진다.
  • 승자의 수 bb가 주어진다. 경기가 무승부면 b=0b = 0이다. (0≤b<a)(0\leq b < a)
  • 승자 번호 q_1,⋯ ,q_bq\_1, \cdots, q\_b가 주어진다. 이들은 p_1,⋯ ,p_ap\_1, \cdots, p\_a 중 서로 다른 정수다.

출력

모든 학생의 가능한 전략 조합의 수를 109+710^9+7로 나눈 나머지를 출력한다.

예제3

  1. 예제 1

    입력
    3 3
2 1 2 / 1 1
2 2 3 / 1 2
3 1 2 3 / 0
    예상 출력
    27

  2. 예제 2

    입력
    3 1
2 1 2 / 0
    예상 출력
    243

  3. 예제 3

    입력
    3 3
2 1 2 / 1 1
2 2 1 / 1 1
2 1 2 / 0
    예상 출력
    0