만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

요새 방어

시간 제한2초메모리 제한1024 MB

요약
h×w 격자 안에 서로 점을 공유하지 않는 사각형 방어선을 중첩하는 모든 경우를 세고, 각 경우의 방어 수준 합을 10^9+7로 나눈 나머지로 구합니다.
난이도

보통10점 중 7점

유형
조합론, 동적 계획법, 수학
정답자
아직 제출이 없습니다

문제

플랫랜더 사람들은 정사각형 칸으로 이루어진 격자 위에 요새를 짓고 있다. 요새에는 여러 겹의 방어선이 있다. 각 방어선은 칸의 경계를 따라 놓인 직사각형이다.

첫 번째 바깥 방어선은 h×wh \times w 크기의 직사각형이다. 다음 방어선은 이전의 모든 방어선보다 엄격히 안쪽에 있다. 방어선끼리는 공통된 점이 없어야 한다.

칸의 방어 수준은 그 칸이 안에 놓인 방어선의 개수이다. 요새의 방어 수준은 모든 칸의 방어 수준을 더한 값이다. 예를 들어 그림의 요새 방어 수준은 16⋅1+8⋅2+3=3516 \cdot 1 + 8 \cdot 2 + 3 = 35이다.

플랫랜더 사람들은 요새를 지을 수 있는 모든 방법에 관심이 있다. 각 방법마다 방어 수준을 구하고, 모든 방법의 값을 합한다. 이 합을 구해 보자. 답이 클 수 있으므로 109+710^9 + 7로 나눈 나머지를 출력한다.

입력

첫 줄에 두 정수 hh와 ww (1≤h,w≤4001 \le h, w \le 400)가 주어진다.

출력

모든 방법의 방어 수준 합을 109+710^9 + 7로 나눈 나머지를 한 정수로 출력한다.

힌트

첫 번째 예제의 요새를 지을 수 있는 모든 방법은 그림과 같다.

두 번째 예제의 요새를 지을 수 있는 모든 방법은 그림과 같다.

예제2

  1. 예제 1

    입력
    3 3
    
    예상 출력
    19
    
  2. 예제 2

    입력
    5 5
    
    예상 출력
    1060