No.1561 connect x connect
Problem Statement
There is a grid of $\ N\times M\ $ cells. The cell in the $i$-th row from the top and the $j$-th column from the left is called $\ (i,\ j)\ $.
Initially, no cell is colored. You will now choose $1$ or more cells and paint them black to make a poster of size $N\times M$.
Here, an "attractive poster" is defined as follows.
First, a poster with only $1$ cell painted black is an "attractive poster".
When $2$ or more cells are painted black, the poster is an "attractive poster" if they are all connected. That is, it satisfies the following condition.
Find the number of "attractive posters" and output it modulo $1000000007$.
Here, $2$ posters $\ A,B\ $ are considered different if there exists a cell $\ (x,\ y)\ $ such that exactly one of the cell $\ (x,\ y)\ $ of $A$ and the cell $\ (x,\ y)\ $ of $B$ is painted black; in that case, $\ A,B\ $ are different.
Constraints
Input
$N\ M$
Output
Find the number of "attractive posters" and output it modulo $1000000007$.
Print a newline at the end.
Sample
Sample 1
Input
2 2
Output
13
There are $2^4-1=15$ ways to paint $1$ or more of the $2\times 2=4$ cells,
but among them, those with only $2$ diagonal cells painted are not "attractive posters". There are $2$ such ways, as shown in the figure.
All the others are "attractive posters", so the answer is $15-2=13$.
Sample 2
Input
5 6
Output
45280509
Sample 3
Input
7 77
Output
713420418
Find the answer modulo $1000000007$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2
shinchan
maspy
nok0