시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.4 초 1024 MB539816.000%

문제

Elly has a squared sheet of paper with N rows and M columns. The girl wants to fill each of the squares with red or blue. She insists that each square with a certain color has at least one more square with the same color in the same row or the same column ("so it does not feel alone").

For each square it is enough to have a matching-by-color square either оn the same row OR on the same column – but not necessarily both (although this is allowed). It is also allowed there to be more than one matching square in the same row or column – for example an entire row filled with red is okay. It is not required that both colors are used – thus the whole paper being blue for example might be a valid filling.

The girl now wonders in how many ways she can fill the sheet of paper. Two ways of filling are considered different, if there is a cell that is colored red in one of filling and blue in another.

입력

On the only line of the standard input are given two integers N and M – the number of rows and columns of the paper, respectively.

출력

On the standard output, print one integer: the number of different ways to fill the paper. Since the answer can be rather large, print only its remainder when divided by 1 000 000 007.

서브태스크

번호배점제한
130

1 ≤ N, M ≤ 5

230

1 ≤ min(N, M) ≤ 7

340

1 ≤ N, M ≤ 50

예제 입력 1

3 3

예제 출력 1

284

예제 입력 2

5 4

예제 출력 2

898416

예제 입력 3

13 17

예제 출력 3

390317257

예제 입력 4

42 42

예제 출력 4

193467102

채점 및 기타 정보

  • 예제는 채점하지 않는다.