Neçə prefiksli?

1920-ci illərdə polyak riyaziyyatçısı Yan Lukaseviç cəbr ifadələri üçün mötərizəsiz yazılış olan Poland notasiya sistemini (Polish notation) təqdim etmişdi. Prefix (Polish) notasında operator həmişə operandlardan əvvəl yerləşir. Məsələn, (b-c/d)/(e*f-(g+h*k)) infiks (adi) if adəsinin segmenti $c/d$ üçün prefix yazılış $/cd$ olur, b-c/d üçün isə $-b/cd$. e*f üçün $\ast ef$, h*k üçün $\ast hk$ və g+h*k üçün +g*hk alınır. Beləliklə, e*f-(g+h*k) ifadəsi prefix formasında -*ef+g*hk şəklindədir və bunları birləşdirib son bölmə əməliyyatı üçün tam prefix ifadə /-b/cd-*ef+g*hk alınır.

Verilmiş $N$ tam ədədi (1 \leq N \leq 50) üçün yalnız ikili əməliyyatları (“+”, “-”, “*”, “/”) və tələb olunan sayda unikal hərfləri — ya Qədim Gürcü əlifbasının ilk hərfləri, ya Müasir Ukrayna əlifbasının son hərfləri, ya da hər ikisinin təkrarsız kombinasiya formasında istifadə edərək uzunluğu $N$ olan mümkün prefix (Polish) ifadələrinin sayını təyin edin. Cavab $1000009$ modulu üzrə hesablanmalıdır. Bütün mümkün prefix ifadələri, operandlar olaraq $e$ ədədinin doqquzuncu onluq təsvirinin onluq hissəsinin $753$-cü rəqəmindən başlayaraq uyğun sayda ardıcıl rəqəm götürülməsi ilə alınan dəyərlərin azalmaya doğru sıralanmasına əsasən düzülür. Dəqiqlik üçün, cavab sabit seçilmiş tələb olunan sayda unikal hərfdən ibarət dəst üçün hesablanır.

**Qeyd.** Qəbul edilmiş, sübut edilmiş fakt kimi, Müasir Ukrayna və Qədim Gürcü əlifbalarında ümumi hərflər yoxdur.