역사학자인 KOI 교수는 이전에 존재했던 IOI 왕국에 대해 연구하고 있다. 과거의 조사에 따르면, IOI 왕국은 세로 H 크기에 가로 W 크기이며, IOI 왕국의 수도는 방어를 위해 성벽으로 둘러싸여 있었다.

IOI 왕국의 수도를 둘러싸는 성벽은 다음과 같은 형태를 하고 있다:

- 성벽의 크기 s(s ≥ 3)가 있다. - 크기 s의 성벽은 s × s의 정사각형 영역에서 안의 (s-2) × (s-2) 정사각형 영역을 제외한 테두리 모양을 하고 있다.

또 다른 조사에 의하면, 수도를 둘러싼 성벽의 크기는 L 이상이었다. 그리고 어떤 칸들에는 오래된 나무가 있는데, 나무가 있는 위치에는 성벽이 존재하지 않았음을 알고 있다.

KOI 교수는 이러한 사실들을 바탕으로 있을 수 있는 성벽의 가지 수를 알고 싶어한다. 이 때, 성벽의 크기가 같더라도 위치가 다르면 서로 다른 성벽으로 간주한다.

IOI 왕국의 크기와, 성벽의 최소 크기, 그리고 나무의 위치들이 주어졌을 때 가능한 성벽의 가지 수를 구하는 프로그램을 작성하시오.

IOI 왕국 timer 5s memory 512MB

IOI 왕국 5s 512MB