ReflectiveRectangle | Topcoder Archive

Problem Statement

Raymond has a rectangle with dimensions sideA times sideB. The sides of the rectangle are perfect mirrors. There is a directional light source in one corner of the rectangle. Raymond can point the light source in any direction. (I.e., he can choose any angle strictly between 0 and 90 degrees. The chosen angle does not have to be an integer.) When Raymond turns the light source on, it will shine a ray of light into the rectangle. The light follows the law of reflection: whenever it hits a mirror, the angle of incidence equals the angle of reflection.

Raymond's goal is to shine the ray of light in the following way:

The light must bounce off the sides of the rectangle exactly bounces times, without hitting a corner of the rectangle.
After exactly that many bounces, the light must reach the opposite corner.

Raymond found all solutions to the above problem. In other words, he found all choices of the initial angle that lead to the desired outcome. He then took a sheet of paper. For each of the solutions, he computed the square of the distance the light traveled before hitting the opposite corner, and he wrote down the result. (Note that the squared distance is always an integer.)

You are given the ints sideA, sideB, and bounces. Return the sum of all numbers on Raymond's paper, modulo 10^9 + 7.

Definition

Class:: ReflectiveRectangle
Method:: findSum
Parameters:: int, int, int
Returns:: int
Method signature:: int findSum(int sideA, int sideB, int bounces)
(be sure your method is public)

Constraints

sizeA will be between 1 and 10^6, inclusive.
sizeB will be between 1 and 10^6, inclusive.
bounces will be between 0 and 10^9, inclusive.

Examples

```
3
```
```
4
```
```
0
```
```
Returns: 25
```
As there should be 0 bounces, Raymond has to point the light source directly at the opposite corner. The squared length of that light beam will be 3^2 + 4^2 = 25.
```
3
```
```
3
```
```
2
```
```
Returns: 180
```
There are two possible paths, each with squared length 90.
```
13
```
```
17
```
```
1
```
```
Returns: 0
```
Sometimes, it is not possible to find any valid path that satisfies the conditions.
```
59325
```
```
31785
```
```
262142
```
```
Returns: 48032850
```
Don't forget to take the answer modulo 10^9+7.

1000000000

Returns: 145972110

Be careful with overflow.

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.