Скільки префіксних?

У 1920-х роках польський математик Ян Лукашевич запропонував позначення алгебраїчних виразів без дужок, яке отримало назву польського запису. У префіксному (польському) записі оператор розташовується перед операндами. Наприклад, якщо інфіксний вираз має вигляд (b-c/d)/(e*f-(g+h*k)), то префіксна форма фрагмента $c/d$ — це $/cd$, а для b-c/d — $-b/cd$. Фрагмент e*f буде $\ast ef$, h*k — $\ast hk$, а g+h*k — +g*hk. Таким чином, вираз e*f-(g+h*k) набуває вигляду -*ef+g*hk у префіксному записі, а підставивши все разом для фінальної операції ділення, повний префіксний вираз — /-b/cd-*ef+g*hk.

Задано ціле число $N$ (1 \leq N \leq 50). Визначте число, яке дорівнює загальній кількості можливих префіксних виразів довжини $N$, використовуючи лише бінарні операції '+', '-', '*', '/' та необхідну кількість унікальних літер — або перші літери старогрузинської абетки, або останні літери сучасної української абетки, або їхню комбінацію без повторів. Результат слід обчислити по модулю $1000009$, враховуючи, що всі можливі префіксні вирази, які задовольняють зазначеним умовам, впорядковані у спадному порядку за значенням, отриманим, якщо операнди брати як відповідну кількість послідовних цифр з дев'ятого десяткового запису числа $e$, починаючи з $753$-ї цифри дробової частини. Щоб уникнути неоднозначностей, підрахунок відповіді проводиться для фіксованого набору необхідної кількості унікальних літер.