25610번 - 영희의 심부름

스눕스 고등학교의 반장 영희는 선생님이 주신 심부름을 해야 한다. 심부름의 내용은 학교 어딘가의 철수에게 가서, 교무실로 가라는 말을 전하는 것이다.

하지만 영희는 당장 다음 교시의 숙제인 수학 익힘책 풀이를 해야 해서 심부름을 할 시간이 없다. 그래서 영희는 학교 곳곳에 자신이 숨겨둔 사탕과 초콜릿의 위치가 표시된 비밀 지도를 빌려줄 테니, 대신 심부름을 해 줄 수 있는지 케레에게 물어보았다.

비밀 지도의 모습은 다음과 같다.

• 지도는 N × N의 격자 형태이며, 각 칸은 학교의 한 구역을 의미한다.
• 각 칸에서는 상하좌우로 움직일 수 있으며, 상하좌우의 칸 사이 거리는 모두 일정하다.
• 사탕이 있는 구역은 o, 초콜릿이 있는 구역은 x로 표시되어 있으며 아무 것도 없는 구역은 별다른 표시가 없다.

케레의 심부름 과정은 구체적으로 아래와 같다. “무작위로 고른다”는 가능한 선택지 중 하나를 모두 같은 확률로 고른다는 것을 의미한다.

1. 제일 왼쪽 위의 칸에서 시작해서 철수의 위치에 도달하는 최단 경로 중 1개 이상의 사탕 또는 초콜릿을 지나가는 경로들의 집합 S을 구한다.
2. S가 공집합이면 케레는 0개의 사탕과 초콜릿을 얻게 된다. S가 공집합이 아니라면, 집합의 경로 중 하나를 무작위로 고른다. 이 경로를 따라 이동하며 모든 사탕과 초콜릿을 얻는다.

제안을 들은 케레는, 이 지도를 사용하여 심부름을 수행하는 동안 얻을 수 있는 사탕의 기댓값과 초콜릿의 기댓값을 알아보고 싶었다.

하지만 큰 문제가 있는데, 그것은 철수의 위치를 아직 모른다는 것이다. 따라서 철수가 어떤 구역에든 있을 수 있다고 생각하고, 가능한 모든 위치에 대해서 사탕의 기댓값의 평균과 초콜릿의 기댓값의 평균을 구하고자 한다.

또한, 지도의 몇몇 구역의 경우 영희가 무언가를 숨긴 것은 확실하지만, 이것이 사탕인지 초콜릿인지 잘못 표기했던 구역이 있다. 어떠한 칸 (r, c)의 정보가 잘못되었다는 제보가 들어올 때마다, 지도를 수정하고 케레에게 수정된 지도에서의 기댓값의 평균을 알려주자.

첫째 줄에 격자의 크기 N(1 ≤ N ≤ 1 000)이 주어진다.

다음 N개의 줄에 문자열 s_i가 주어진다. s_i의 j번째 문자는 지도의 i행 j열에 담긴 정보를 의미한다.

• .: 해당 구역에 아무 것도 없음
• o: 해당 구역에 사탕이 있음
• x: 해당 구역에 초콜릿이 있음

다음 줄에 지도 정정 제보의 수 Q(1 ≤ Q ≤ 100 000)가 주어진다.

다음 Q개의 줄에 두 정수 r_i, c_i(1 ≤ r_i, c_i ≤ N)가 주어진다.

이는 지도의 (r_i, c_i) 위치의 정보가 초콜릿이었다면 사탕으로, 사탕이었다면 초콜릿으로 변경해야 함을 의미한다.

(r_i, c_i)는 최초 지도에서 .이 아닌 위치였음이 보장된다.

기댓값의 평균은 다음과 같이 출력한다. M = 998 244 353이라 할 때, 기댓값의 평균의 기약 분수 표현이 A / B 이면 A ⋅ B^M−2을 M으로 나눈 나머지를 출력하시오. 철수의 위치에 관계없이 심부름 1단계에서의 집합 S의 크기는 0이거나 M과 서로소임이 보장된다.

첫째 줄에 최초의 지도에서 심부름을 하면서 얻을 수 있는 사탕의 기댓값의 평균과 초콜릿의 기댓값의 평균을 공백을 사이에 두고 한 줄에 출력한다.

둘째 줄부터 Q개의 줄에 걸쳐 지도가 수정된 이후의 사탕의 기댓값의 평균과 초콜릿의 기댓값의 평균을 공백을 사이에 두고 한 줄에 출력한다.

구체적으로는, 모든 1 ≤ i ≤ Q에 대해 (i + 1)번째 줄에 1번째부터 i번째까지의 수정 사항을 적용한 지도에서의 사탕의 기댓값의 평균과 초콜릿의 기댓값의 평균을 공백을 사이에 두고 한 줄에 출력한다.

최초의 지도에서 사탕의 기댓값의 평균을 계산하는 과정은 다음과 같다.

• 철수가 1행 1열에 있다면, 사탕과 초콜릿이 있는 최단 경로가 없으므로 영희는 0개의 사탕을 얻는다.
• 철수가 1행 2열에 있는 경우도 마찬가지로 0개의 사탕을 얻는다.
• 철수가 2행 1열에 있다면, 사탕과 초콜릿이 있는 최단 경로는 아래로 한 칸 내려가는 것뿐이다. 이 경로에서 영희는 1개의 사탕을 얻는다.
• 철수가 2행 2열에 있다면, 사탕과 초콜릿이 있는 최단 경로는 ‘ㄱ’자 모양 경로와 ‘ㄴ’자 모양 경로 두 가지이다. ‘ㄱ’자 모양 경로에서는 사탕을 얻을 수 없고, ‘ㄴ’자 모양 경로에서는 사탕을 1개 얻으므로, 얻을 수 있는 사탕의 기댓값은 0.5개이다.

따라서 기댓값의 평균은 (0 + 0 + 1 + 0.5) ÷ 4 = 3/8이므로, 3 ⋅ 8^{M − 2}을 M으로 나눈 나머지인 623 902 721을 출력한다.

비슷한 방법으로 최초의 지도에서 초콜릿의 기댓값의 평균이 (0 + 0 + 0 + 1) ÷ 4 = 1/4임을 알 수 있고, 따라서 1 ⋅ 4^{M − 2}을 M으로 나눈 나머지인 748 683 265를 출력한다.

첫 번째 정정 제보 이후 지도에는 초콜릿이 없으므로 초콜릿의 기댓값의 평균은 0이다.

두 번째 정정 제보 이후 지도의 상태는 최초의 지도 상태와 같으므로, 첫 번째 줄과 세 번째 줄의 출력 값은 완전히 같다.