Tablica

시간 제한1초메모리 제한2048 MB

요약

각 행과 각 열에 1이 하나 또는 둘씩 들어가는 N x M 0/1 행렬의 개수를 10^9+7로 나눈 나머지를 구한다.

난이도: 어려움10점 중 9점
유형: 조합론, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

Promatramo tablice s $N$ redaka i $M$ stupaca koje sadrže samo brojeve $0$ i $1$ . Tablica je dobra ako se u svakom retku nalaze ili jedna ili dvije jedinice te se i u svakom stupcu nalaze ili jedna ili dvije jedinice. Odredite ostatak pri dijeljenju broja dobrih tablica s $N$ redaka i $M$ stupaca, s $10^9 + 7$ .

입력

U prvom retku su prirodni brojevi $N$ i $M$ .

출력

U jedini redak potrebno je ispisati ostatak pri dijeljenju s $10^9 + 7$ broja dobrih tablica.

힌트

Pojašnjenje prvog probnog primjera:

Sve dobre tablice s $2$ retka i $2$ stupca:

예제3

예제 1
입력
```
2 2
```
예상 출력
```
7
```
예제 2
입력
```
3 3
```
예상 출력
```
102
```
예제 3
입력
```
15 20
```
예상 출력
```
415131258
```