JOI 村にある広い荒れ地には N 体のかかしが立っており,村民は年に数回,かかしたちを囲ってお祭り を行っていた.あるとき,かかしたちのお告げを聞いたという JOI 村の村長は,荒れ地に畑を 1 つ作る計 画を立てた.お告げによると,畑は以下の条件を満たすべきであるという:
- 各辺が,東西方向あるいは南北方向であるような長方形である.
- 南西の頂点および北東の頂点には,かかしが立っている.
- 畑の内部 (境界を除く) には,かかしは立っていない.
もちろん,大切なかかしたちを動かすことは許されない.お告げに従った畑の場所はいくつあるだろうか.
かかしたちの位置が与えられたとき,お告げに従った畑の場所の個数を求めるプログラムを作成せよ.