만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

흑백 그림

시간 제한1초메모리 제한128 MB

요약
n×m 체커판에서 오른쪽 아래 칸이 흰색인 8×8 블록의 개수를 센다. 그림 오른쪽 아래 칸의 색이 주어진다.
난이도

쉬움10점 중 3점

유형
수학, 조합론, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

현대 미술 작품이 가득한 미술관을 구경하고 있습니다. 그중 한 그림은 오직 검은색과 흰색 정사각형만으로 이루어져 있으며, 정사각형들이 체스판처럼 행과 열을 이루도록 배치되어 있어 변을 맞대고 인접한 두 칸은 서로 다른 색을 가집니다.

심심해진 당신은 이 그림 안에 8×88 \times 8 체스판이 몇 개나 들어 있는지 세어 보기로 했습니다. 여기서 8×88 \times 8 체스판이란 그림에서 연속한 88개의 행과 연속한 88개의 열이 이루는 임의의 블록을 뜻하며, 그 블록의 오른쪽 아래 모서리 칸은 반드시 흰색이어야 합니다.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 세 정수 nn, mm, cc가 주어지는 한 줄로 구성됩니다 (8≤n,m≤400008 \le n, m \le 40000). nn은 그림의 행 개수, mm은 그림의 열 개수입니다. cc는 00 또는 11이며, 00은 그림의 오른쪽 아래 모서리 칸이 검은색임을, 11은 그 모서리 칸이 흰색임을 나타냅니다.

마지막 테스트 케이스 다음에는 세 개의 00으로 이루어진 줄이 주어지며, 이 줄은 입력에 포함되지 않으므로 처리하면 안 됩니다.

출력

각 테스트 케이스마다, 주어진 그림 안에 들어 있는 8×88 \times 8 체스판의 개수, 즉 오른쪽 아래 모서리 칸이 흰색인 (연속한 88개의 행과 연속한 88개의 열로 이루어진) 블록의 개수를 한 줄에 하나씩 출력하세요.

예제1

  1. 예제 1

    입력
    8 8 0
    8 8 1
    9 9 1
    40000 39999 0
    0 0 0
    
    예상 출력
    0
    1
    2
    799700028