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
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.
1000000
1000000
1000000000
Returns: 145972110
Be careful with overflow.
493285
816238
223092868
Returns: 507599497
3*5*7*11*...*23*2-2
734123
571842
536870912
Returns: 283488121
2^29-2
993829
181
999999984
Returns: 999277825
large prime*2-2
593743
827182
469948592
Returns: 148717757
238371
837482
181892818
Returns: 633283324
539892
178371
49310921
Returns: 0
61675
3147
647197746
Returns: 525377637
30662
51068
197281796
Returns: 127277701
64321
13886
487786798
Returns: 464856448
98100
35618
583508182
Returns: 753355162
38648
58764
347949104
Returns: 112261812
91480
13530
851856524
Returns: 929977096
69398
70053
539584782
Returns: 568575649
56048
89890
869406830
Returns: 588242233
17830
40694
33643140
Returns: 771581607
97785
80081
397485666
Returns: 527817012
68157
51005
548022356
Returns: 613617439
15874
91878
503352370
Returns: 641020729
91315
13222
347977324
Returns: 621200146
65496
60413
84211208
Returns: 633736236
15518
33671
373556548
Returns: 414346520
70752
26504
621337906
Returns: 225312938
44114
34680
933516482
Returns: 885444007
50668
34961
40428092
Returns: 325939878
53515
1340
967234990
Returns: 796250562
13879
87771
727573842
Returns: 429488424
87828
73297
108373294
Returns: 680957413
66105
58725
7494980
Returns: 320503695
16324
1044
803799078
Returns: 293055342
41691
75576
510117506
Returns: 471418980
57208
27834
100342952
Returns: 626162513
59491
16159
970994382
Returns: 950030184
92330
51480
446444500
Returns: 720640687
43821
82625
877477900
Returns: 868029392
96535
9885
736166488
Returns: 22911248
83313
97708
592420216
Returns: 183358958
116
26195
604293028
Returns: 660564794
570
67266
876320866
Returns: 200764245
59326
35845
652542588
Returns: 36154224
10775
30764
162453738
Returns: 811629513
67736
1268
321949064
Returns: 909674674
80977
56219
202158534
Returns: 722051447
38325
39523
733203228
Returns: 104871070
97687
56932
333121384
Returns: 970570135
84051
43191
187585186
Returns: 338531108
78861
16180
285414444
Returns: 98903748
1
1
931170238
Returns: 439533890