Neçə prefiksli?
Məlumdur ki, XX əsrin 20-ci illərində polyak riyaziyyatçısı Yan Lukasyeviç (Jan Lukasiewicz) onun şərəfinə polyak yazıları adlandırılan mötərizəsiz alqebraik ifadələrin yazılış formalarını təklif etmişdir. Prefiks polyak yazısı əməliyyat işarəsinin müvafiq operandlardan (operanddan) əvvəl yerləşdirilməsi ilə əldə edilir. Məsələn, əgər infiks ifadə (b-c/d)/(e*f-(g+h*k)) formasındadırsa, "c/d" fraqmentinin prefiks forması "/cd", "b-c/d" fraqmentinin prefiks forması "-b/cd" olacaqdır. "e*f" fraqmentinin prefiks forması "*ef", "h*k" fraqmentinin prefiks forması "*hk", və "g+h*k" fraqmentinin prefiks forması isə "+g*hk" olacaqdır. Beləliklə, "e*f-(g+h*k)" ifadəsinə prefiks yazı "-*ef+g*hk" uyğun gələcək və alınan prefiks yazıları son əməliyyat - bölmə kimi operandlar olaraq qəbul edərək, nəticədə belə bir ifadə əldə edəcəyik: "/-b/cd-*ef+g*hk".
Bizə verilən tam N (1 ≤ N ≤ 50) üçün yalnız iki operandlı əməliyyatları '+', '-', '*', '/' və həmçinin qədim gürcü əlifbasının ilk hərflərinin və ya müasir Ukrayna əlifbasının son hərflərinin, ya da hər ikisinin təkrarlanmayan və lazım olan sayda hərflərini ehtiva edən bütün mümkün prefiks ifadələrinin ümumi sayına bərabər olan bir rəqəmi müəyyən etmək tapşırığı verilib. Bu rəqəm 1 000 009 moduluna görə alınır, şərti ilə ki, bütün mümkün prefiks ifadələri, verilmiş şərtlərə cavab verən, daha böyük dəyərlərin alınması ardıcıllığı ilə sıralanmışdır, əgər operandlar olaraq Nömrə Nəpər sayının onluq hissəsinin 753-cü rəqəmindən başlayaraq ardıcıl gələn rəqəmlərdən lazım olan sayda alınırsa. Qeyri-müəyyənliyi aradan qaldırmaq üçün vurğulayaq ki, axtarılan rəqəm təkrarlanmayan hərflərin lazım olan sayının sabit dəsti üçün hesablanır.
Qeyd. Müasir Ukrayna və qədim Gürcü əlifbalarının ortaq hərflərinin boş çoxluq olduğunu sübut edilmiş tezis kimi qəbul edəcəyik.
Giriş verilənləri
Fayl bir sıra - N ədədini ehtiva edir.
Çıxış verilənləri
Fayl tək bir rəqəm (aydındır ki, tam :) ) - axtarılan nəticəni ehtiva edir.