SplittingFoxes | Topcoder Archive

Problem Statement

Fox Ciel learned a new skill of splitting! She can split into (S + L + R) foxes each time. Now she is practicing this skill on an infinite horizontal plane. At the beginning, Fox Ciel is the only fox on the plane. She stands at the point (0,0) and she is facing the point (1,0).

There will be n steps. In each step, each fox on the plane will split into exactly (S + L + R) foxes. Out of those foxes:

S will make a step forward, moving exactly one unit of distance in the direction they are facing.
L will stay in the same place and rotate 90 degrees to the left. (So for example if the original fox was facing the point (1,0), there will be L new foxes facing the point (0,1).)
R will stay in the same place and rotate 90 degrees to the right.

The score of a fox standing at the point (x,y) is x*y. Note that the score of a fox may be zero or even negative. The total score is the sum of the scores of all foxes on the plane. You are given the long n and the ints S, L, and R. Return the total score of all foxes after n steps, modulo 1,000,000,007 (10^9 + 7).

Definition

Class:: SplittingFoxes
Method:: sum
Parameters:: long, int, int, int
Returns:: int
Method signature:: int sum(long n, int S, int L, int R)
(be sure your method is public)

Notes

Note that you should return a number between 0 and 1,000,000,006, inclusive.
E.g., if the answer is -1, you should return 1,000,000,006 instead of -1.

Constraints

n will be between 1 and 10^18, inclusive.
S will be between 0 and 10^9, inclusive.
L will be between 0 and 10^9, inclusive.
R will be between 0 and 10^9, inclusive.

Examples

```
58
```
```
2
```
```
0
```
```
0
```
```
Returns: 0
```
After step 1: there are 2^1 foxes at (1, 0), After step 2: there are 2^2 foxes at (2, 0), ... After step 58: there are 2^58 foxes at (58, 0). For each fox at (58, 0), her score is 58 * 0 = 0, so the answer is 0.
```
3
```
```
1
```
```
1
```
```
0
```
```
Returns: 1
```
There will be 8 foxes at the end. The fox at (1,1) has score 1. Each of the other 7 foxes has score 0.
```
5
```
```
1
```
```
3
```
```
2
```
```
Returns: 34
```
```
5
```
```
1
```
```
2
```
```
3
```
```
Returns: 999999973
```
The answer is (-34) % 1,000,000,007.
```
123456789
```
```
987654321
```
```
544
```
```
544
```
```
Returns: 0
```
By symmetry, if L = R, then the answer will be zero.
```
65536
```
```
1024
```
```
512
```
```
4096
```
```
Returns: 371473914
```

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.