Sıra
Orisya n^2 hərfdən ibarət kvadrat şəklində n * n ölçüsündə bir kağız hazırlayıb və bəzi hərfləri bir xətt boyunca silmək istəyir. O, sol üst küncdən başlayaraq sağa və ya aşağıya doğru hərəkət edərək xətt çəkir və sağ alt küncdəki hərflə bitir. Beləliklə, Orisya dəqiq 2n - 1 hərf siləcək. Bu prosesdə, xətt boyunca müəyyən bir sehrli sözün yazılmasını istəyir.
Verilən hərflərin yerləşdirilməsi və sehrli söz əsasında, Orisyanın bu sözü neçə fərqli şəkildə silə biləcəyini müəyyən edən və nəticəni 1 000 003 ədədinə bölünmənin qalığı olaraq verən bir proqram yazın.
Giriş məlumatları
Birinci sətirdə təbii ədəd n (2 ≤ n ≤ 1000) - hərflərlə dolu kvadratın tərəfinin uzunluğu verilir. Sonrakı n sətirdə hər biri n kiçik latın əlifbası hərfi (mütləq fərqli deyil) verilir, bu da hərflərin yerləşdirilməsini göstərir. Hərflər arasında boşluq yoxdur. Daha sonra 2n - 1 hərfdən ibarət sehrli söz verilir (kiçik latın əlifbası hərfləri, mütləq fərqli deyil).
Çıxış məlumatları
Orisyanın sehrli sözü neçə fərqli şəkildə silə biləcəyinin sayını 1 000 003 ədədinə bölünmənin qalığı olaraq tək bir ədəd çıxarın.
Nümunə
"logos" sözünü silmək üçün dəqiq 5 yol mövcuddur:
