Payız parkı

Vəzir günü, səhər. Olimpiadaya getmək vaxtıdır. Veniamin bir dəstə təmiz kağız, qələm, bir neçə sendviç götürdü — başqa nə lazım olacaq? — və hara və necə çatacağını öyrənmək üçün kartoqrafik saytı açdı. Nə xoşbəxtlik! Yolda gözəl bir park var və Veniamin parkda gəzməyi çox sevir. Park kvadrat hüceyrələrə bölünmüş düzbucaqlı bir sahədir, hər birində ya çəmənlik və yollar, ya da bir maneə (kollar, ağaclar və ya hətta hasarlanmış bir abidə) var.

Olimpiadaya vaxtında gəlmək lazımdır, ona görə də Veniamin parkda uzun müddət gəzməyə imkan verə bilməz. Parkın yan-yana olan iki hüceyrəsi arasında hərəkət etmək bir saniyə çəkir. Veniamin yerində dayana bilmir, ona görə də hər saniyə yan-yana olan bir hüceyrəyə keçir. Veniamin qərara gəldi ki, özünə əlavə iki saniyə gəzməyə icazə verə bilər. Sizin vəzifəniz: parkdan keçmək üçün yolların sayını hesablamaqdır ki, gəzinti vaxtı minimumdan dəqiq iki saniyə çox olsun.

Parkın girişi və çıxışı parkda müəyyən edilmiş fərqli hüceyrələrdir, parkın sərhədlərindən kənara çıxmaq qadağandır, yalnız yan-yana olan hüceyrələr arasında hərəkət etmək olar. Veniamin girişdən çıxışa keçidin optimal vaxtından iki saniyə daha çox gəzməlidir, ona görə də o, yolun aralıq nöqtəsi kimi girişdə və ya çıxışda ola bilər. Çünki məsələnin cavabı olduqca böyük ola bilər, sizdən yolların sayının 10^9+9 ilə bölünməsindən qalanı tələb olunur.