Farmer Johnは $M \times N$ の牧草地を購入しました. 各牧草地のマスは肥沃であるか, 不毛であるかのどちらかです.
ここでFarmer Johnは牛たちのためにとうもろこしを栽培することにしました. 一マスで育てられるとうもろこしは一つだけで, なおかつそれぞれのマスは一つの牛だけに割り当てられることになります. 牛たちは窮屈な状態で食事をするのが嫌なので, 互いに辺を共有するようなマス同士ではとうもろこしを同時に育てることはできません. また当然のことながら不毛な土地ではとうもろこしを育てることができません.
このような条件下でとうもろこしを育てるマスを選ぶ方法はいくつあるでしょうか. 100000000で割った余りを答えてください.

2016-07-09

PKU JudgeOnline 1274 - The Perfect Stall

PKU JudgeOnline 二部マッチング

問題

http://poj.org/problem?id=1274

$N$ 頭の牛と $M$ のstallが存在しています. 各牛にはお気に入りのstallがあり, そこに入っている時しかミルクを出してくれません. 各stallには一頭の牛しか入れることはできないため, Farmer Johnはなるべく多くのミルクを手に入れるような割り当て方をしたいです.
そのような割り当て方をした時, 何頭の牛からミルクを手に入れることができるでしょうか.