H. Пары гномов

По кругу сидят $2n$ гномов, места пронумерованы от 0 до $2n - 1$. Каждому раздали от одной до $c$ монет.

Таня разглядывает пары гномов, сидящих напротив друг друга. Она довольна, если найдётся такое $i$ ($0 \le i < n$), что $a_i + a_{i+n} \ne s$.

Посчитайте количество раздач, при которых Таня довольна.

Число «плохих» пар придётся посчитать самому — оно зависит и от $c$, и от $s$.

Одна строка содержит числа $n$ ($1 \le n \le 10^5$), $c$ ($1 \le c \le 10^6$) и $s$ ($2 \le s \le 2 \cdot 10^6$).

Одно число — количество раздач по модулю $10^9 + 7$.