Palindromik yollar

Kvadrat cədvəl n × n ölçüsündə verilir və bu cədvəl təbii ədədlərdən ibarətdir. Biz cədvəlin sol üst küncündən sağ alt küncünə yalnız sağa və aşağıya doğru hərəkət etməklə (heç vaxt sola və ya yuxarıya deyil) gedən yolları nəzərdən keçirəcəyik. Belə bir yol boyunca 2n - 1 ədəd yerləşir. Əgər bir yolun üzərindəki ədədlər dəsti "simmetrik"dirsə, yəni tərsinə oxunduqda da eyni qaydada oxunursa, bu yolu palindromik adlandıracağıq.

Tapşırıq

Verilmiş cədvəldəki palindromik yolların ümumi sayını tapın.

Giriş məlumatları

Girişin ilk sətrində cədvəlin ölçüsü olan tam ədəd n: 2 ≤ n ≤ 100 verilir. Sonrakı n sətirdə cədvəli təyin edən n təbii ədəd verilir və bu ədədlər 10 000-dən böyük deyil.

Çıxış məlumatları

Çıxış yalnız bir ədəd olmalıdır: verilmiş cədvəldəki palindromik yolların sayının 101-ə bölünməsindən alınan qalıq.

Şərh

Birinci nümunədə dörd palindromik yol mövcuddur:

1. sağa — sağa — aşağıya — aşağıya (7–10–5–10–7);

2. sağa — aşağıya — sağa — aşağıya (7–10–8–10–7);

3. aşağıya — sağa — aşağıya — sağa (7–5–8–5–7);

4. aşağıya — aşağıya — sağa — sağa (7–5–8–5–7).

İkinci nümunədə 252 mümkün yolun hər biri palindromikdir, buna görə 252-nin 101-ə bölünməsindən alınan qalıq 50-dir və bu nəticə çıxışda göstərilməlidir.