Under construction

Still being built. Things may change

Black and White Painting

Time limit1sMemory limit128 MB

Summary
Count the 8x8 blocks inside an n by m checkerboard whose bottom-right square is white, given the color of the painting's bottom-right corner.
Level

Easy3 of 10

Topics
Math, Combinatorics, Implementation, Brute force
Solved
No attempts yet

Statement

You are visiting an art museum full of modern paintings. One painting consists solely of black and white squares arranged in rows and columns like a chessboard, so that no two squares that share an edge have the same colour.

Because you are bored, you start to wonder how many 8×88 \times 8 chessboards are embedded within this painting. Here an embedded 8×88 \times 8 chessboard is any block of 88 consecutive rows and 88 consecutive columns of the painting, and its bottom-right corner square must always be white.

Input

The input contains several test cases. Each test case is a single line with three integers nn, mm and cc (8≤n,m≤400008 \le n, m \le 40000): nn is the number of rows of the painting and mm is the number of columns. The value cc is 00 or 11, where 00 means the bottom-right corner square of the painting is black and 11 means that corner square is white.

The last test case is followed by a line containing three zeros, which is not part of the input and must not be processed.

Output

For each test case, print on its own line the number of 8×88 \times 8 chessboards embedded within the given painting — that is, the number of blocks of 88 consecutive rows and 88 consecutive columns whose bottom-right corner square is white.

Examples1

  1. Example 1

    Input
    8 8 0
    8 8 1
    9 9 1
    40000 39999 0
    0 0 0
    
    Expected output
    0
    1
    2
    799700028