Quadratic Function

Time limit2sMemory limit1024 MB

Summary

Given f(x)=(x-a)(x-b), pick n-1 interior points with increasing x between a and b to maximize the area of their convex polygon, printed modulo 1000000007.

Level: Medium7 of 10
Topics: Dynamic programming, Geometry, Math
Solved: No attempts yet

Problem

A quadratic function $f(x) = (x-a)(x-b)$ is given.

Place $n+1$ points on the graph $y = f(x)$ , namely $(x_0, f(x_0)), (x_1, f(x_1)), \cdots, (x_n, f(x_n))$ , where $a = x_0 < x_1 < x_2 < \cdots < x_n = b$ . Find the maximum area of the convex polygon formed by these $n+1$ points.

For every input, the answer is always a rational number.

Input

The first line contains an integer $n$ . ( $2 \leq n \leq 1\,000$ )

The second line contains two integers $a$ and $b$ . ( $0 \leq a < b \leq 1\,000$ )

Output

Let the maximum area be $\frac{p}{q}$ , where $p$ and $q$ are coprime positive integers. Print the integer $v$ with $0 \leq v \leq 1\,000\,000\,006$ such that $q \cdot v \equiv p \pmod{1\,000\,000\,007}$ .

Such $v$ always exists for every input.

Examples3

Example 1
Input
```
3
0 3
```
Expected output
```
4
```
Example 2
Input
```
2
0 1
```
Expected output
```
125000001
```
Example 3
Input
```
13
17 99
```
Expected output
```
361038099
```