Double Cross Count in a Binary Matrix

In the C Tribe, the double cross (双十字) is an important tribal symbol. A double cross is formed by two horizontal line segments of ones and one vertical line segment of ones that intersect the horizontal segments exactly at their centers. Formally, a valid double cross must satisfy the following conditions:

1. The two horizontal segments must not be in consecutive rows.
2. Each horizontal segment is a contiguous group of ones in a single row. Its length must be odd so that it has a unique center. If a horizontal segment starts at column (a) and has length (L), then its center is at column (a+\frac{L-1}{2}). The vertical segment, when it crosses the horizontal segment, must divide it into two equal halves.
3. The vertical segment is a contiguous column of ones. If the vertical segment spans from row (u) to row (v), then it must have (u < r_{top}) and (v > r_{bottom}), where (r_{top}) and (r_{bottom}) are the rows of the top and bottom horizontal segments, respectively.
4. The center column of the two horizontal segments must be identical (so that the vertical segment exactly intersects the centers of both horizontal segments).
5. The top horizontal segment must be strictly shorter than the bottom horizontal segment.

Given an (R \times C) binary matrix (composed of characters '0' and '1'), count the number of valid double crosses in the matrix. Since the answer can be very large, output it modulo (10^9+9).

Note: All formulas are in LaTeX format. For example, the modulus is expressed as (10^9+9).

inputFormat

The first line contains two integers (R) and (C), representing the number of rows and columns of the matrix. Each of the next (R) lines contains a string of length (C) composed only of characters '0' and '1', representing the matrix.

outputFormat

Output a single integer representing the number of valid double crosses in the matrix, taken modulo (10^9+9).

sample

1 1
1

0