## JOI '18 Spring Camp Day 1 P3 - Tents

View as PDF

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

Problem types

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

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 and (, ) are occupied by tents, then the entrance of the tent in the section () must be directed to south, and the entrance of the tent in the section must be directed to north.
• If both of the two sections and (, ) are occupied by tents, then the entrance of the tent in the section must be directed to east, and the entrance of the tent in the section 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 and . This means that the campsite ran by JOI-kun is divided into rows and 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 .

#### Constraints

All input data satisfy the following conditions.

#### 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