Problem 1686: nuz

Ion şi Ana se amuză construind cuvinte formate din litere mari ale alfabetului englez: A, B, $\dots$ , Z. Aceștia îşi imaginează o nouă limbă care admite cuvinte conţinând subsecvenţe formate din aceeaşi literă. Ei au impus totuși o restricţie: niciun cuvânt nu trebuie să înceapă cu litera Z. De exemplu, fie cuvântul: AAZCCCCADDDBBBBEEC. Cuvântul nu începe cu Z. El poate fi descompus în subsecvenţe formate din litere identice: AA Z CCCC A DDD BBBB EE şi C. Dintre acestea, CCCC şi BBBB au lungimea $4$ . Numim subsecvenţe repetabile maximale cele mai lungi subsecvenţe formate din litere identice. Deci, în exemplul de mai sus, CCCC şi BBBB sunt subsecvenţe repetabile maximale.

Întrebarea pe care şi-o pun acum Ion şi Ana este următoarea: care este numărul (modulo $30 \ 011$ ) de cuvinte formate din cel mult $n$ litere mari ale alfabetului englez, care conţin cel puţin o secvenţă repetabilă maximală de lungime $k$ . Atenție, cuvintele nu vor putea conține secvențe repetabile de lungime strict mai mare decât $k$ .

Cerinţă

Cunoscând $n$ și $k$ , lungimea maximă a unui cuvânt și respectiv lungimea unei secvenţe repetabilă maximală, să se determine numărul de cuvinte care se pot forma, modulo $30 \ 011$ .

Date de intrare

Fişierul de intrare nuz.in conține pe prima linie numerele $n$ şi $k$ având semnificaţia din enunţ.

Date de ieșire

Fişierul de ieșire nuz.out va conţine pe o singură linie un număr natural ce reprezintă numărul de cuvinte ce se pot forma conform cerinţei.

Restricții și precizări

$2 \leq K \leq N \leq 100 \ 000$
pentru $50\%$ din teste $N \leq 1 \ 000$

Exemplul 1

nuz.in

2 2

nuz.out

Explicație

Exista $25$ de secvenţe: AA, BB, CC, $\dots$ , YY

Exemplul 2