Dr. Farrell is planning team practices to prepare his students for the next regional contest. He wants all of his students to get experience practicing together so that they can share knowledge and avoid the situation where the whole team graduates at once and leaves no one for the next year.

To facilitate this practice, he has booked a bifurcated room where students can practice in two seperate groups. This allows him to monitor both groups simultaniously, and to direct students to switch groups so that they can get experience working with different people. The practice will be held in hour-long segments, and after each hour he can direct a small number of students to switch groups. However, he wants everyone to be together at the front of the room for the first and last hour to explain the practice and to debrief at the end.

# Add a graphic that shows a room split into front and back where group A is in the front and group B is in the back.

Each student can be classified as either a problem solver or a problem coder depending on their strengths. To minimize foot traffic, Dr. Farrell will direct at most one student of each type to switch groups at the end of each hour.

Dr. Farrell has also prepared a small number of challenge problems that he plans to present to a group at various points throughout the practice. As the problems have various difficulties, he has predetermined the number of problem solvers and problem coders that are needed to solve the problem within the hour. Since there is some overlap in skills between problem solvers and problem coders, there might also be a combined minimum number of students needed to solve the problem that is greater than the sum of the number of solvers and coders. Dr. Farrell wants to structure the teams so that all challenge problems are solved during the practice.

How many ways can Dr. Farrell direct the students to switch teams to ensure that the contraints are met? Output the answer modulo 1e9+7.

- Everyone starts and ends in team A.
- At most 2 people switch teams at the end of each hour (one student of each type).
- All challenge problems are solved.

Rough sample input

n = duration of the practice in hours (3 <= n <= 10^18)
p = number of challenge problems (1 <= p <= 10)
s = number of problem solvers
c = number of problem coders (1 <= s,c <= 20)

```
10 2 3 4      # n, p, s, c - 10 hour practice with 2 challenge problems, 3 problem solvers and 4 problem coders
2 A 1 2 4     # 2 hours into the practice, he will give group A a challenge problem requiring 1 solver, 2 coders, and 4 people in total to solve
5 B 2 1 3     # 5 hours into the practice, he will give group B a challenge problem requiring 2 solvers, 1 coder, and 3 people in total to solve
```

Expected solution runtime of O(p * log n * (s^3 + c^3)).

Optionally output -1 if meeting the constraints is impossible instead of 0.

Note: I can change the lore later, I just thought this was funny.