Cüt olmayan sayda müstəqil çoxluqlara malik ağaclar

Sizə təbii ədəd $n$ (n \leq 1000) və sadə ədəd $p$ (10^7 < p < 10^9) verilir. Tapşırığınız odur ki, köklü ağacların (qeyri-işarələnmiş köklü ağacların) neçə dənəsinin müstəqil kəsmlərinin sayı təkdir, onu müəyyən edəsiniz. Cavabı $p$-yə görə qalıqla çap edin.

Köklü ağac o ağaca deyilir ki, bir zirvə kök kimi seçilib və istənilən zirvənin oğullarının sırası nəzərə alınmır. Yəni, iki ağac eyni sayılır, əgər kök olmayan zirvələrin yerini dəyişmək (sırasını dəyişmək) nəticəsində onlar eyni olarsa. Daha dəqiq desək, iki köklü ağac T_1 və T_2 yalnız o halda eyni sayılır ki, T_1-in zirvələrindən T_2-nin zirvələrinə bijektiv funksiya $f$ mövcud olsun, $f$ T_1-in kökünü T_2-nin kökünə köçürsün və T_1-dəki hər bir $(u,v)$ kənarı üçün T_2-də (f(u), f(v)) kənarı mövcud olsun.

Qrafın (bəzən boş olan) zirvələrindən ibarət altlıq müstəqil kəsm adlanır, əgər bu altlıqda heç iki zirvə qonşu deyilsə.