Zadanie

Jaroslav túto úlohu nedokončil

Počet bodov: 70

Jaroslav dostal \(n\)-strannú kocku a úlohu: koľko rôznych postupností hodov touto kockou má súčet \(s\)?

Ale Jaroslav je lenivý a túto úlohu nedokončil, tak ju išiel dať do zenitu. Ale ani to nedokončil, takže ju teraz pripravujem do zenitu ja.

Ale vyriešte si ju už vy. Teda ak chcete body. Neskutočne originálna motivácia.

Úloha

Máme \(n\)-strannú kocku so stranami \(1\) až \(n\). Môžeme ňou hádzať a sčítavať hody. Koľko postupností hodov existuje, že ich súčet je \(s\)? Postupnosti sú rôzne ak majú rôzne dĺžky, alebo ak v niektorom hode padlo na kocke iné číslo.

Keďže počet postupností môže byť veľký, vypíšte ho modulo \(10^9+7\).

Vstup a Výstup

V jedinom riadku vstupu sú kladné čísla \(n\) a \(s\). Postupne pre ne platí:

\(n \le 6\) a \(s \le 20\)

\(n \le 6\) a \(s \le 1000\)

\(n \le 6\) a \(s \le 5 \cdot 10^7\)

\(n \le 100\) a \(s \le 5 \cdot 10^7\)

\(n \le 100\) a \(s \le 10^{18}\) (3 sady)

Príklad

Input:

6 4

Output:

8

Je 8 postupností hodov so súčtom 4 pomocou 6strannej kocky. Sú to: \([1, 1, 1, 1]\), \([1, 1, 2]\), \([1, 2, 1]\), \([1, 3]\), \([2, 1, 1]\), \([2, 2]\), \([3, 1]\), \([4]\)

Input:

6 47

Output:

951202719

Je 951202719 (mod \(10^9+7\)) postupností hodov so súčtom 47 pomocou 6strannej kocky. Sú to: načítavam…