Əlifba şorbası
Piter evdə nahar edir. Təəssüf ki, bu gün yemək şorba olacaq. Piterin anası onun şorbanı çox sevmədiyini bildiyi üçün xüsusi bir şorba hazırlayıb. Bu şorbada əlifba hərfləri, rəqəmlər və digər simvollar şəklində makaron parçaları var. Anasının xüsusi bir bıçağı var və onunla s fərqli formada məhdudiyyətsiz miqdarda makaron parçası hazırlaya bilər. Şorbada həmişə p makaron parçası var və şorba o qədər qalındır ki, parçalar heç vaxt hərəkət etmir.
Anasının səylərinə baxmayaraq, Piter bu günkü menyudan narazıdır və həyatında neçə gün şorba yeməli olacağını düşünür. Anası ona hər gün yeni bir şorba hazırlayacağını və heç bir gün əvvəl təqdim olunan şorbadakı bütün mövqelərdə eyni formalara malik olmayacağını vəd edir. Lakin p makaron parçalarının sayı və onların üzmə mövqeləri hər gün eyni qalacaq. Piteri aldatmaq asan deyil (ən azı o belə düşünür) və o, bacarıqla başa düşür ki, bu hələ də onu sonsuzadək şorba yeməyə məcbur edə bilər. Konfiqurasiyaların sayını azaltmaq üçün, anasına əvvəlcədən gördüyü konfiqurasiyalardan birini döndərərək əldə edilə bilən heç bir yeməyi qəbul etməyəcəyini deyir.
Şəkil 1: Piterin yeməyinə yuxarıdan baxış
Tabağı mərkəzi koordinatların başlanğıcında olan radiusu 2 olan dairə kimi düşünün. Bütün simvollar verilmiş bucaq altında (milligradusla) koordinatların başlanğıcından 1 məsafədə şorbada üzəcək. İki qab bərabər sayılır, əgər bir qabı mərkəzi ətrafında döndərərək simvolların mövqeləri və simvolların özləri hər iki qabda eyni olarsa.
Proqramınız Piterin anasının əlində olan mümkün simvolların sayını və hər bir makaron parçasının yerləşməsini təyin edən bucaqları (milligradusla saat əqrəbi istiqamətində ölçülür) alacaq. Anasının hazırlaya biləcəyi mümkün qabların sayını qaytaran proqram yazın. Bu rəqəm çox böyük ola biləcəyi üçün, 10^8 + 7 moduluna görə rəqəmi çıxarın, bu sadədir.
Giriş məlumatları
Hər testdə ilk sətir iki rəqəm ehtiva edir: s (2 ≤ s ≤ 1000) - Piterin anasının istifadə edə biləcəyi simvolların sayı; və p (p > 0) - şorbada üzən makaron parçalarının sayı. Növbəti p sətirin hər biri p hissələrindən birinin bucağını a (0 ≤ a < 360000) ehtiva edir (milligradusla saat əqrəbi istiqamətində ölçülür). Bütün bucaqlar fərqlidir.
Testlər arasında boş sətir var. Son testdən sonra s = p = -1 olan bir sətir gəlir.
Çıxış məlumatları
Hər test üçün ayrı sətirdə bir tam ədəd çıxarın - Piterin anasının hazırlaya biləcəyi fərqli qabların sayı 10^8 + 7 moduluna görə.