Зростаючі підпослідовності

Послідовність $p(1)$, $p(2)$, …, $p(N)$, що складається з чисел $1$, $2$, … , $N$, називається перестановкою, якщо всі елементи в послідовності різні.

Перестановка $p$ містить зростаючу підпослідовність з $k$ елементів, якщо існують індекси

такі, що

Якщо перестановка $p$ має зростаючу підпослідовність з $B$ елементів, але не має жодної з B+1 елементів, то число $B$ називається ступенем зростання цієї перестановки.

Вам потрібно створити програму, яка, отримавши число $N$, обчислює кількість перестановок, ступінь зростання яких дорівнює $B$. Оскільки кількість таких перестановок може бути дуже великою, необхідно обчислити її залишок від ділення на $1000000000$.