Məşq (Qızıl)

Fermer Con (yenə) inəklər üçün yeni səhər idman rejimi icad edib!

Əvvəlki kimi, fermer Conun n inəyi sıraya düzülüb. Soldan i-ci inək hər bir i üçün i etiketinə malikdir (1 ≤ i ≤ n). O, inəklərə deyir ki, inəklər başlanğıcda olduğu kimi eyni sıraya düzülənə qədər aşağıdakı addımı təkrarlasınlar.

Uzunluğu n olan A permutasiyası verilir, inəklər öz sıralarını elə dəyişirlər ki, dəyişiklikdən əvvəl soldan i-ci inək dəyişiklikdən sonra soldan A[i]-ci olur.

Məsələn, əgər A = (1, 2, 3, 4, 5) olarsa, inəklər bir addım atır. Əgər A = (2, 3, 1, 5, 4) olarsa, inəklər altı addım atacaq. Hər addımdan sonra soldan sağa inəklərin sırası belə olacaq:

0 addım: (1, 2, 3, 4, 5)

1 addım: (3, 1, 2, 5, 4)

2 addım: (2, 3, 1, 4, 5)

3 addım: (1, 2, 3, 5, 4)

4 addım: (3, 1, 2, 4, 5)

5 addım: (2, 3, 1, 5, 4)

6 addım: (1, 2, 3, 4, 5)

Uzunluğu n olan permutasiya üçün inəklərin məhz k addım atmasını tələb edən bütün müsbət tam ədədlərin k cəmini tapın.

Bu ədəd çox böyük ola biləcəyi üçün cavabı m modulu ilə verin.

Giriş məlumatları

Bir sətirdə n (1 ≤ n ≤ 10^4) və m (10^8 ≤ m ≤ 10^9 + **7`, m sadə) ədədləri verilir.

Çıxış məlumatları

Bir ədəd çıxarın.

Nümunə

İnəklərin 1, 2, 3, 4, 5 və 6 addım atmasını tələb edən permutasiyalar mövcuddur. Cavab 1 + 2 + 3 + 4 + 5 + 6 = 21-dir.