Tehtäväsi on laskea, montako eri tapaa on sijoittaa $n \times n$ -kokoiselle shakkilaudalle $k$ lähettiä niin, että mikään lähetti ei uhkaa toista.

Shakissa lähetit uhkaavat toisiaan, jos ne ovat samalla viistorivillä.

Esimerkiksi jos $n=5$ ja $k=4$, yksi mahdollinen ratkaisu on:

Syöte

Syötteessä on kaksi kokonaislukua $n$ ja $k$: laudan koko ja lähettien määrä.

Tuloste

Ohjelmasi tulee tulostaa erilaisten tapojen määrä modulo $10^9+7$.

Esimerkki 1

Syöte:

5 4

Tuloste:

2728

Esimerkki 2

Syöte:

10 10

Tuloste:

915225111

Osatehtävä 1 (12 pistettä)

• $1 \le n \le 5$
• $1 \le k \le n^2$

Osatehtävä 2 (23 pistettä)

• $1 \le n \le 10$
• $1 \le k \le n^2$

Osatehtävä 3 (65 pistettä)

• $1 \le n \le 100$
• $1 \le k \le n^2$