크리스마스 이브의 밤, 정원 위로 불꽃이 피어오르고 있다. 붉고 푸른 빛이 밤하늘에 펼쳐지는 동안, 다다스는 정원에서도 그 빛이 함께 춤추기를 바랐다.
다다스가 준비한 조명은 관람객들이 직접 불빛의 배치를 바꿀 수 있다. 하늘의 불꽃놀이를 바라보며, 정원에도 저마다의 빛을 펼쳐 보는 것이다.
정원에는 번부터 번까지 번호가 붙은 조명이 있다. 조명들은 개의 양방향 오솔길로 연결되어 있다. 각 오솔길은 서로 다른 두 조명을 직접 연결하며, 오솔길을 따라 어떤 조명에서든 다른 모든 조명으로 이동할 수 있다.
각 조명은 빨간색으로 켜져 있거나, 파란색으로 켜져 있거나, 꺼져 있다. 장면은 빨간 조명 개, 파란 조명 개, 꺼진 조명 하나로 이루어진 조명 상태의 배치이다. 두 장면에서 어느 한 조명의 상태라도 다르면 서로 다른 장면이다.
관람객들은 제어장치로 다음 조작을 할 수 있다.
서로 다른 세 조명 를 고른다. 번 조명과 번 조명 사이, 번 조명과 번 조명 사이에는 각각 오솔길이 있어야 한다. 또한, 세 조명은 빨간 조명, 파란 조명, 꺼진 조명을 하나씩 포함해야 한다.
고른 세 조명의 상태를 한 칸씩 순환시킨다. 순환 방향은 자유롭게 고를 수 있다. 즉, 조작 직전 번 조명의 상태가 각각 라면, 세 상태를 동시에
로 바꾼다. 나머지 조명의 상태는 바뀌지 않는다.
제어장치에는 조명 연출의 시작점이 될 장면들을 저장할 수 있다. 관람객은 저장된 장면 하나를 불러온 뒤, 위 조작을 반복하며 원하는 장면을 만들어 간다.
다다스는 관람객들이 가능한 모든 장면을 연출할 수 있도록 저장할 장면들을 고르려고 한다. 어떤 장면을 만들고 싶더라도, 저장된 장면 중 하나를 불러온 뒤 위 조작을 번 이상 반복하여 그 장면을 만들 수 있어야 한다. 목표 장면마다 서로 다른 저장 장면을 불러와도 된다.
이 조건을 만족시키기 위해 저장해야 하는 장면 수의 최솟값을 구하라. 답이 매우 클 수 있으므로 으로 나눈 나머지를 출력하라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스에 대하여:
각 테스트 케이스마다, 가능한 모든 장면을 만들기 위해 저장해야 하는 장면 수의 최솟값을 으로 나눈 나머지를 한 줄에 출력한다.
조명의 상태를 번호순으로 나열하여 장면을 나타내자. R, B, □는 각각 빨강, 파랑, 꺼짐을 뜻한다.
첫 번째 테스트 케이스에서는 RB□와 R□B 두 장면을 저장하면 된다.
이것이 가능한 여섯 장면의 전부이다. 한 장면만 저장해서는 여섯 장면을 모두 만들 수 없으므로 답은 이다.
두 번째 테스트 케이스에서는 □RBB 한 장면만 저장해도 가능한 열두 장면을 모두 만들 수 있으므로 답은 이다.
첫째 줄에 테스트 케이스의 개수 가 주어진다.
각 테스트 케이스의 첫째 줄에 조명의 개수 과 빨간 조명의 개수 이 주어진다.
이어지는 개의 줄에 오솔길이 직접 연결하는 두 조명의 번호가 주어진다. 번 오솔길은 번 조명과 번 조명을 직접 연결한다. 이면 오솔길을 나타내는 줄은 주어지지 않는다.