댄스타임
시간 제한1초메모리 제한1024 MB
우진이 앞을 보면 같은 춤, 뒤를 보면 다른 춤을 추어야 하고, 최대 한 번만 규칙을 어길 수 있을 때 가능한 춤 순서의 수를 센다.
문제
호영이는 기대하던 WooJeans의 팬미팅에 가게 되었다. 팬미팅의 하이라이트인 댄스타임에서는 마지막 라운드를 통과한 팬에게 사인 앨범을 주는데, 열혈팬 호영이도 사인 앨범을 받기 위해 열심히 춤 연습을 하고 있다.
댄스타임은 개의 라운드로 이루어져 있으며, 각 라운드에는 WooJeans의 리더 우진이 바라보는 방향에 따라 올바른 춤을 춰야 한다. 댄스타임의 각 라운드에서 올바른 춤을 췄다는 것은 아래와 같이 춤을 추는 것을 뜻한다.
- 우진이 앞을 보고 춤을 추면 호영이는 우진과 같은 춤을 춰야 한다.
- 우진이 뒤를 보고 춤을 추면 호영이는 우진과 다른 춤을 춰야 한다.
댄스타임에서는 최대 한 번까지 올바르지 않은 춤을 추더라도 해당 라운드를 통과할 수 있다. 즉, 두 번 이상 올바르지 않은 춤을 추면 즉시 해당 라운드에서 떨어지게 된다.
호영이가 마지막 라운드까지 통과하여 사인 앨범을 받을 수 있는 경우의 수를 구해보자. 이때, 적어도 하나의 라운드에서 호영이가 추는 춤의 종류가 다르면 다른 경우이며, WooJeans의 열혈팬 호영이는 우진이 출 모든 춤을 알고 있다.
입력
첫째 줄에 댄스타임의 라운드 개수 , 우진이 출 춤 종류의 개수 이 공백으로 구분되어 주어진다.
둘째 줄부터 번째 줄까지 각각의 줄에 우진이 추는 춤의 종류와 우진이 춤을 추는 동안 바라보는 방향을 나타내는 두 정수 , 가 공백으로 구분되어 주어진다.
우진은 가 이면 앞, 이면 뒤를 바라보고 춤을 춘다.
출력
첫째 줄에 호영이가 사인 앨범을 받을 수 있는 경우의 수를 소수 로 나눈 나머지를 출력하라.