[Medium] AkariDaisukiDiv1

g(n) = f^n(S) 라고 하자. 그러면 g(n) = W + g(n-1) + A + g(n-1) + D 이다. h(n) = g(n) 에서 F가 등장하는 횟수 라고 하자. 우리가 계산해야하는 값은 h(k) 이다. g(n) 에 g(n-1) 이 2번 등장하므로 h(n) = 2*h(n-1) + C(n) 의 형태일 것이다. 여기서 C(n) 은 다음과 같다. C(n) = ( W + g(n-1) 에 등장하며, W와 겹치는 영역이 있는 F의 개수 ) + ( g(n-1) + A + g(n-1) 에 등장하며, A와 겹치는 영역이 있는 F의 개수 ) + ( g(n-1) + D 에 등장하며, D와 겹치는 영역이 있는 F의 개수 ) 만약 n이 충분히 크다고 하면 (최소 50 초과) W + g(n-1) 의 맨 앞은 WWWWW... 같은 식이 될 것이며 g(n-1) + D 의 맨 뒤는 ...DDDDD 같은 식이 될 것이며 g(n-1) + A + g(n-1) 의 중간 부분은 ...DDDDAWWWW... 같은 식이 될 것이므로 C(n)은 값이 변하지 않는다. 따라서 50정도 까지는 시뮬레이션으로 h(n)을 구하고 그 뒤부터는 h(n) = 2*h(n-1) + (상수) 이므로 빠르게 h(k) 를 계산할 수 있다. 시뮬레이션을 할 때 len(g(50)) >= 2^50 이므로 g(n) 을 전부 들고 있을 수 없다. g(n) 의 prefix와 suffix를 유지하면서 C(n) 을 잘 계산해야한다.