AtCoder Beginner Contest 037

lines = $stdin.read
array = lines.split("\n")
H,W   = array[0].split(" ").map(&:to_i)
A     = array[1..H+1].map{|s| s.split(" ").map(&:to_i)}
 
#require 'matrix'
#dp = Matrix.build(H,W){|row,col| 0}.to_a
dp = Array.new(H).map{Array.new(W){0}}
 
def rec(dp,i,j,sq,h,w)
  #puts "i=#{i},j=#{j},h=#{h},w=#{w}"
  if dp[i][j] == 0
    ans = 1
    if i > 0 and sq[i][j] < sq[i-1][j]
      ans += rec(dp,i-1,j,sq,h,w) # up
    end
    if i < h-1 and sq[i][j] < sq[i+1][j]
      ans += rec(dp,i+1,j,sq,h,w) # down
    end
    if j > 0 and sq[i][j] < sq[i][j-1]
      ans += rec(dp,i,j-1,sq,h,w) # left
    end
    if j < w-1 and sq[i][j] < sq[i][j+1]
      ans += rec(dp,i,j+1,sq,h,w) # right
    end
    ans
  else
    dp[i][j]
  end
end
 
for i in 0...H
  for j in 0...W
    dp[i][j] = rec(dp,i,j,A,H,W)
  end
end
 
puts dp.inject(&:+).inject(&:+)

lines = $stdin.read
array = lines.split("\n")
$H,$W = array[0].split(" ").map(&:to_i)
$A    = array[1..$H+1].map{|s| s.split(" ").map(&:to_i)}
$MOD   = 10**9 + 7
 
$dy = [1,0,-1,0]
$dx = [0,1,0,-1]
 
$dp = Array.new($H).map{Array.new($W){-1}}
 
def dfs(y, x)
  if $dp[y][x] != -1
    $dp[y][x]
  else
    ans = 1
    for i in 0...4
      ny = y + $dy[i]
      nx = x + $dx[i]
 
      next if not (0 <= ny and ny < $H and 0 <= nx && nx < $W)
 
      if $A[y][x] < $A[ny][nx]
        ans += dfs(ny, nx)
        ans = ans % $MOD
      end
    end
    $dp[y][x] = ans
    ans
  end
end
 
ans = 0
 
for i in 0...$H
  for j in 0...$W
    #dp[i][j] = rec(dp,i,j,A,H,W)
    #ans += $dp[i][j]
    ans += dfs(i,j)
    ans = ans % $MOD
  end
end
 
puts ans

#
# very sorry, hatovalley
# https://beta.atcoder.jp/contests/abc037/submissions/1497549
#
lines = $stdin.read
array = lines.split("\n")
H,W   = array[0].split(" ").map(&:to_i)

# add empty areas around the matrix
A = [Array.new(W+2, 0)]
H.times do |r|
  A << [0] + array[1+r].split(" ").map(&:to_i) + [0]
end
A << Array.new(W+2, 0)

MOD = 10**9+7

dp = Array.new(H + 2) do |i|
  Hash.new do |h, j|
    v = A[i][j]
    u = A[i + 1][j] > v ? dp[i + 1][j] : 0
    d = A[i - 1][j] > v ? dp[i - 1][j] : 0
    r = A[i][j + 1] > v ? dp[i][j + 1] : 0
    l = A[i][j - 1] > v ? dp[i][j - 1] : 0
    h[j] = (u + d + r + l + 1) % MOD
  end
end

ans = 0

for i in 1..H
  for j in 1..W
    #puts "dp[#{i}][#{j}] = #{dp[i][j]}"
    ans += dp[i][j]
  end
  ans %= MOD
end

puts ans