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