TheFourSquares | Topcoder Archive

Problem Statement

Manao has a rectangular board of height n and width m. He is trying to put four squares in the corners of the board in such a way that:

Each square is aligned to the sides of the board and exactly one of its vertices coincides with a vertex of the board.
The length of the side of each of the squares is a positive integer.
No pair of squares intersects. Note that some pairs of squares may touch each other.

Manao is interested in how many ways can he choose the lengths of the sides for his squares. More precisely, he is interested in the number of quadruples (a, b, c, d) such that if the square in the top-left corner of the board has side length a, the square in the bottom-left corner has side length b, the square in the top-right corner has side length c and the square in the bottom-right corner has side length d, they do not intersect.

You are given the ints n and m. Compute and return the number of valid quadruples modulo 1,000,000,009.

Definition

Class:: TheFourSquares
Method:: countPlacements
Parameters:: int, int
Returns:: int
Method signature:: int countPlacements(int n, int m)
(be sure your method is public)

Constraints

n will be between 2 and 1,000,000, inclusive.
m will be between 2 and 1,000,000, inclusive.

Examples

```
2
```
```
2
```
```
Returns: 1
```
The only valid quadruple is (1, 1, 1, 1).
```
3
```
```
3
```
```
Returns: 5
```
The five valid quadruples are: (1, 1, 1, 1). (1, 1, 1, 2). (1, 1, 2, 1). (1, 2, 1, 1). (2, 1, 1, 1).
```
3
```
```
4
```
```
Returns: 9
```
In addition to the five quadruples from the previous sample, there are four new quadruples here: (1, 2, 1, 2). (1, 2, 2, 1). (2, 1, 1, 2). (2, 1, 2, 1).
```
10
```
```
7
```
```
Returns: 421
```
```
123456
```
```
987654
```
```
Returns: 136415012
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.