Neçə şablon?

Aritmetik ifadələri mötərizəsiz yazmaq mümkündür. Əgər əməliyyat operandlardan sonra yazılırsa, bu postfix yazılış adlanır, operandlardan əvvəl yazılırsa, prefix yazılış adlanır. Məsələn, a-b*c ifadəsi postfix olaraq abc*-, prefix olaraq isə -a*bc şəklində yazılır.

Aritmetik ifadənin mötərizəsiz formasının şablonu dedikdə, 0, 1, 2 və 3 rəqəmlərindən ibarət olan bir sıra nəzərdə tutulur. Burada 0 operandı, qalan rəqəmlər isə əməliyyatları ifadə edir. Rəqəmin böyüklüyü müvafiq əməliyyatın yerinə yetirilməsi üçün lazım olan operandların sayını göstərir.

Şablon həm postfix, həm də prefix ola bilər.

Verilmiş şablon uzunluğu N üçün yalnız 0 və 3 simvollarının istifadə oluna biləcəyi uzunluğu N olan düzgün prefix şablonlarının ümumi sayını müəyyən edin. Cavabı 1000000009 (10^9+9) moduluna görə verin.