No.1561 connect x connect
タグ : / 解いたユーザー数 8
作問者 :
noya2
/ テスター :
uwi
shinchan
maspy
nok0
問題文
$\ N\times M\ $のマス目があります。このマス目の、上から $i$ 番目の左から $j$ 番目のマスを$\ (i,\ j)\ $と呼ぶことにします。
はじめ、各マスに色は塗られていません。今から $1$ つ以上のマスを選んで黒に塗って $N\times M$ の大きさのポスターを作ります。
ここで、「映えるポスター」を以下のように定めます。
まず、 $1$ マスのみが黒に塗られたポスターは「映えるポスター」です。
$2$ マス以上が黒に塗られているとき、それらがすべて連結ならば、そのポスターは「映えるポスター」です。 すなわち、以下の条件を満たすものです。
「映えるポスター」が何通りあるかを求め、 $1000000007$ で割った余りを出力してください。
ただし、 $2$ つのポスター$\ A,B\ $について、あるマス$\ (x,\ y)\ $が存在して、 $A$ のマス$\ (x,\ y)\ $と $B$ のマス$\ (x,\ y)\ $のうち一方のみが黒に塗られているとき、$\ A,B\ $は異なるものとします。
制約
入力
$N\ M$
出力
「映えるポスター」が何通りあるかを求め、 $1000000007$ で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 2
出力
13
$2\times 2=4$ マスを $1$ つ以上塗る塗り方は $2^4-1=15$ 通りありますが、
そのうち斜め $2$ マスだけが塗られたものは「映えるポスター」ではありません。これは図のように $2$ 通りあります。
それ以外は「映えるポスター」ですから、 $15-2=13$ が答えとなります。
サンプル2
入力
5 6
出力
45280509
サンプル3
入力
7 77
出力
713420418
$1000000007$ で割った余りを求めてください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。