# Earthquake!

Limits: 1s, 512 MB

Most houses are not as safe as they could be. Earthquake engineering is an interdisciplinary branch of engineering that designs and analyzes structures, such as buildings and bridges, with earthquakes in mind. Its overall goal is to make such structures more resistant to earthquakes. US president Mr. Donald J. Trump wants to build a house for her wife. He owns a huge land where he wants to build the house. Unfortunately, the land is terrain and it has a variable elevation. It is shaped like a rectangle, N meters wide and M meters long. It can be divided into N·M squares (see the image). President’s house will be shaped like a rectangle that has sides parallel with the land’s edges and its vertices coincide with the vertices of the squares. All the land covered by President’s house must be of equal elevation to prevent it from collapsing in case of Earthquake. So, you are hired to calculate the number of ways President can build his house for his beautiful wife! You might be rich after solving this problem for Mr. Trump.

This is a companion discussion topic for the original entry at https://toph.co/p/earthquake