歴史学者である JOI 教授は,かつて存在した IOI 王国について研究している.
過去の調査によると,IOI 王国は縦 H 行,横 W 列のマスに区切られた長方形の形をしていた.IOI 王国の首都は,防衛のために城壁で囲われていた.
IOI 王国の首都を囲う城壁は次のような形をしている.城壁には大きさと呼ばれる値が定まっている.大きさ s (s ≥ 3) の城壁とは,s × s の正方形の領域から外周以外の (s − 2) × (s − 2) の正方形の領域を除いたものである.
調査によると,首都を囲う城壁の大きさは L 以上であった.また,IOI 王国のいくつかのマスには城壁が存在しなかったことがわかっている.
JOI 教授は,さらなる研究のために,城壁としてありうるものが何通りあるかを知りたい.
IOI 王国の大きさと,城壁の大きさの最小値,城壁が存在しなかったことが分かっているマスの情報が与えられたとき,城壁としてありうるものは何通りあるかを求めるプログラムを作成せよ.
標準入力から以下のデータを読み込め.
標準出力に,城壁としてありうるものは何通りあるかを表す整数を 1 行で出力せよ.
すべての入力データは以下の条件を満たす.
5 5 3 2 2 2 4 3
4
この入力例の場合,城壁としてありうるものは以下の 4 通りが考えられる.ただし,× で示したマスは城壁が存在しなかったことがわかっているマスである.
7 8 4 3 2 2 3 7 6 5
13
4000 4000 1234 4 1161 3028 596 1892 3731 2606 702 1530
7050792912
問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。