JOI Spring Camp '18 P3 - Tents

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

JOI-kun runs a campsite. This campsite is divided into a rectangular grid of H rows and W columns. The rows are parallel to the east-west direction, and the columns are parallel to the north-south direction. The section in the i-th row from north and j-th column from east is called the section (i, j).

JOI-kun is going to put up some tents in some sections. Each tent must occupy exactly one section. No two tents may occupy the same section. Each tent has one entrance directed to one of the four directions: north, south, east or west. The directions of the entrances of the tents put up in the campsite must satisfy the following conditions.

  • If both of the two sections (i_1, j) and (i_2, j) (1 \le i_1 < i_2 \le H, 1 \le j \le W) are occupied by tents, then the entrance of the tent in the section (i_1, j) must be directed to south, and the entrance of the tent in the section (i_2, j) must be directed to north.
  • If both of the two sections (i, j_1) and (i, j_2) (1 \le i \le H, 1 \le j_1 < j_2 \le W) are occupied by tents, then the entrance of the tent in the section (i, j_1) must be directed to east, and the entrance of the tent in the section (i, j_2) must be directed to west.

JOI-kun became curious about the number of ways to put up at least one tent in the campsite. Two ways to put up tents are distinguished when there exists a section such that the status of the tent in the section (existence of a tent, or the direction of the entrance of the tent).

Input Specification

The first line of input contains two integers H and W. This means that the campsite ran by JOI-kun is divided into H rows and W columns.

Output Specification

Output one integer. The output should contain the remainder of the number of ways to put up at least one tent satisfying the condition described in the problem statement, divided by 10^9 + 7.

Constraints

All input data satisfy the following conditions.

  • 1 \le H \le 3000
  • 1 \le W \le 3000
Subtask Points Additional constraints
1 48 1 \le H,W \le 300
2 52 1 \le H,W \le 3000

Sample Input 1

1 2

Sample Output 1

9

Explanation for Sample 1

Let us denote a tent with the entrance directed to east, west, south and north by the characters E, W, S, N, respectively. There are nine ways to put up some tents as illustrated below

Sample Input 2

4 3

Sample Output 2

3252

Sample Input 3

100 100

Sample Output 3

561068619

Comments

There are no comments at the moment.