Zadanie

Idem byť ako Turista

Počet bodov: 90

Jožko sa rozhodol, že už ho nebaví nebyť najlepším programátorom na svete.

Zabicykloval to teda priamo do Petrohradu za Turistom.

Jožkovi je jasné, že Turista nikdy nebude mať taký prirodzený talent ako on. Jeho jediná výhoda je kvalitná (bielo)ruská výchova a životný štýl. Aké sú najlepšie raňajky pred súťažou? Optimálny šampón na kvalitnejšie debugovanie? Najvhodnejšie ponožky na hľadanie okrajových prípadov? Turista to všetko určite vie, a keby to vedel aj Jožko, hravo by ho porazil.

Jožko podstrčil Turistovi na tréning špionážnu úlohu:

Vypíš, ktoré obchody zajtra navštíviš, a v akom poradí

A získal tak zoznam obchodov, do ktorých Turista chodieva.

Pre jednoduchosť si ich očíslujeme od \(1\) po \(N\) v poradí, v ktorom ich Turista navštevuje.

Jožko pôjde zajtra nakupovať spolu s Turistom. Taktiež navštívi všetky obchody od \(1\) po \(N\).

Na jednu stranu ich nemôže navštíviť v rovnakom poradí - ak by totiž všade chodil s Turistom, určite by si ho Turista všimol, pochopil že ide o konkurenciu, a kupoval by si úplne nevhodné produkty len aby Jožka zmiatol.

Na druhú stranu sa Jožko musí držať blízko pri Turistovi - musí totiž odsledovať jeho návyky (Ako často si vysmrká nos? V ktorom vrecku nosí mobil? Ktorým prstom stláča gombíky vo výťahu?). Preto ak sa Turista práve nachádza v obchode číslo \(a\), Jožko musí byť v takom obchode \(b\), že platí \(|a-b| \leq K\).

Koľko existuje poradí, ktoré spĺňajú Jožkove podmienky?

Vstup a výstup

V jedinom riadku vstupu sú dve celé císla \(N\) a \(K\) - počet obchodov a vzdialenosť, na ktorú sa môže Jožko vzdialiť od Turistu.

Vypíšte jedno číslo: počet poradí, v ktorých Jožko môže navštíviť obchody, nevzdialiť sa od Turistu na viac ako \(K\), a pritom sa líšia od Turistovho poradia.

Formálne, vypíšte počet permutácií \(p_1, p_2, \cdots, p_N\) dĺžky \(N\), pre ktoré platí:

0. Sú to permutácie čísel \(1 \cdots N\)
1. Existuje \(1 \leq i \leq N\) také, že \(p_i \neq i\)
2. Pre všetky \(1 \leq i \leq N\) platí \(|p_i - i| \leq K\)

Keďže toto číslo môže byť obrovské, vypíšte jeho zvyšok po delení \(10^9+7\)

Platí \(1 \leq K \leq 5\).

V prvej sade platí \(1 \leq N \leq 10\).

V druhej \(K=1\) a \(1 \leq N \leq 1\,000\).

V tretej a štvrtej \(1 \leq N \leq 1\,000\).

Príklad

Input:

3 1

Output:

2

Platné poradia sú 1,3,2 a 2,1,3

Input:

3 2

Output:

5

Navyše sú platné 2,3,1, 3,2,1 a 3,1,2

Input:

47 1

Output:

807526947