Downhill Paths

Sejun found a rectangular map while traveling. The map is divided into cells, and each cell represents one location. Each cell contains the height of that location. From any cell, movement is possible only to one of the four neighboring cells that share an edge.

Sejun starts at the upper-left cell and wants to reach the lower-right cell. To spend as little effort as possible, every move must go to a cell with a strictly lower height than the current cell. In the map above, the following three routes are possible.

Given the map, write a program that counts the number of paths from the upper-left cell to the lower-right cell when every move must go downhill.

The first line contains two natural numbers M and N, the height and width of the map, separated by a space. The next M lines contain N natural numbers each, giving the heights of the locations from top to bottom.

M and N are each at most 500. Every height is a natural number at most 10,000.

Print one integer H, the number of possible paths. For every input, H is a non-negative integer not greater than 1,000,000,000.