Юрко və kubiklər#8573
Yurko əşyaları yığmağı və bəzəməyi sevir. Bu gün o, bloklarla işləməyi qərara alıb. Yurkonun blokdan ibarət bir sırada düzülmüş blokları var, soldan sağa doğru -dən -ə qədər nömrələnib və hər birinin üzərində təbii bir ədəd yazılıb. Əlavə olaraq, onun ədəd nida işarəsi olan etiketi var. Məlumdur ki, etiketlərin sayı blokların sayından artıq deyil.
Yurko bir blokun üzərinə etiket qoyarsa, həmin ədəd onun faktoriyalı ilə əvəzlənir. Məsələn, əgər blokun üstündə yazılıbsa, etiket qoyduqdan sonra o 5! = 120 olar.
Sizdən tələb olunur ki, Yurkonun müəyyən blokları olduğu kimi saxlayıb, digərlərinə etiket qoymaqla (ən çox etiket istifadə etməklə), üzərindəki ədədlərin cəmini -ə bərabər etməsinin neçə fərqli üsulu olduğunu hesablayasınız. Qeyd: Hər bir blokda ən çox bir etiket istifadə oluna bilər.
İki üsul yalnız blokların dəyişilməyən və etiket qoyulan dəstləri eyni olduqda eyni sayılır.
Birinci sətirdə üç tam ədəd , , və (1 \leq n \leq 25,\ 0 \leq k \leq n,\ 1 \leq S \leq 10^{16}) — blokların sayı, etiketlərin sayı və tələb olunan cəm verilir.
İkinci sətirdə müsbət tam ədəd a_1,\ a_2,\ \ldots,\ a_n (1 \leq a_i \leq 10^9) — blokların üzərində yazılmış ədədlər verilir. Müxtəlif bloklarda eyni ədəd ola bilər.
Tək bir qeyri-mənfi tam ədəd çap edin — bəzi blokları dəyişmədən saxlayıb və bəzilərinə etiket qoymaqla cəmi -ə bərabər etməyin üsullarının sayını çap edin.
Nümunə 1
Nümunə 2