33814번 - 되먹임 (Feedback) 서브태스크

지구과학을 공부하다보면, 위와 같은 도표를 가끔 발견할 수 있습니다. 위 그림은 "인과지도"라고 하며, 지구 시스템을 이루는 여러 변수들을 시각화하기 위한 도표입니다.

인과지도는 여러 변수를 점으로 나타내고, 두 변수 간 영향을 양(+) 또는 음(-)의 간선의 연결로 표현합니다. 원래 인과지도는 두 변수를 유향간선으로 연결하나, 이 문제에서는 단순히 방향성이 없는 간선으로 연결한다고 생각합시다.

위 그림에서 세 개의 변수, "빙하의 양", "지구의 온도", "지구의 반사도"는 하나의 고리(Cycle)을 이룹니다. 인과지도에서의 고리는 하나의 변수가 변함에 따른 결과가 해당 변수에 다시 영향을 미치는 되먹임(피드백)을 나타내며, 이를 "피드백 루프"라고 부릅니다.

만약 피드백 루프를 이루는 간선 중 음의 간선이 짝수개라면, 어떤 변수의 변화로 인한 결과가 해당 변수의 변화를 더욱 촉진하게 됩니다. 이를 "양의 피드백" 혹은 "악화 피드백"이라고 부릅니다.

지구과학 수업 시작 전, 학생들은 강의실 칠판에 $N$개의 가상의 변수가 하나의 거대한 "피드백 루프"를 구성하는 인과지도를 그리며 놀았습니다. 편의상 이 거대한 피드백 루프를 이루는 변수들에 시계방향으로 $1$부터 $N$까지의 번호를 붙입니다.

수업 종이 치자, 지구과학 수업을 하러 들어오신 이성도 선생님은 칠판을 보고 추가적인 간선 $K$개를 그려 지도를 완성했습니다. 그 결과 어떤 간선도 교차하지 않았으며, 임의의 두 변수 사이를 연결하는 간선이 $2$개 이상 존재하지 않았습니다.

이렇게 완성된 인과지도에서 찾을 수 있는 서로 다른 "악화 피드백"이 몇 개인지 계산하는 프로그램을 작성하세요.

첫째 줄에 변수의 개수 $N$이 주어집니다.

둘째 줄에 처음 있었던 거대한 피드백 루프에 대한 정보가 '+', '-'로 이루어진 $N$자리의 문자열로 주어집니다. $i$번째 문자는 $i$번과 $i+1$번 변수를 연결한 간선의 부호를, $N$번째 문자는 $N$번과 $1$번 변수를 연결한 간선의 부호를 뜻합니다.

셋째 줄에 이성도 선생님이 추가한 간선의 개수 $K$가 주어집니다.

이후 $K$개의 줄에 걸쳐 이성도 선생님이 추가한 간선이 연결한 두 개의 변수의 번호, 그리고 해당 간선의 부호가 띄어쓰기로 구분되어 주어집니다.

완성된 인과지도에 서로 다른 "악화 피드백" 루프의 개수를 출력합니다.

출력값이 너무 클 수 있으므로, $99\,999\,989$으로 나눈 나머지를 출력합니다.

• $3 \leq N \leq 100\,000$
• $0 \leq K \leq N-3$
• 이성도 선생님이 추가한 $K$개의 간선은 위 문제의 조건에 맞게 주어집니다.

• 피드백 루프에 포함되는 변수들의 집합이 서로 다르다면, 다른 피드백 루프로 생각합니다.
• 하나의 변수가 여러 개의 "악화 피드백"에 포함될 수 있습니다.
• 하나의 변수가 한 개의 "악화 피드백"에 여러 번 포함될 수 없습니다.
• 아래와 같은 인과지도에서 "악화 피드백"의 개수는 $2$개입니다: (첫번째 피드백 루프 : $1, 2, 3, 4, 5, 9, 10$번 변수로 구성 / 두번째 피드백 루프 : $1, 2, 5, 6, 7, 8, 9, 10$번 변수로 구성)