산봉우리 등반로

N행 M열의 지도가 주어진다. 각 칸에는 그 지점의 높이가 적혀 있다. 등산객은 항상 더 낮은 높이의 칸으로만 이동할 수 있으며, 상하좌우로 인접한 칸으로만 이동할 수 있다.

가장 왼쪽 위 칸 (0, 0)에서 출발하여 가장 오른쪽 아래 칸 (N-1, M-1)까지 이동하는 경로의 수를 구하시오.

입력

첫째 줄에 N과 M이 공백으로 구분되어 주어진다. (1 <= N, M <= 500)
둘째 줄부터 N개의 줄에 걸쳐 각 칸의 높이가 공백으로 구분되어 주어진다. (1 <= 높이 <= 10,000)

출력

가능한 경로의 수를 출력한다.

입출력 예시

입력 1

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

출력 1

3

입력 2

2 2
3 2
1 0

출력 2

2