Riyaziyyat Ev Tapşırığı#6531
Müəlliminiz sizə yenə çətin bir riyaziyyat tapşırığı verib və siz onu son tarixdən əvvəl tamamlamalısınız.
Bu tapşırıq bölmə əməliyyatı ilə bağlıdır və kiçik ədədlərə bölmə üzrə məşq etməyi tələb edir. Sizdən dəqiq N rəqəmdən ibarət olan (başda sıfırlar ola bilər) və müəyyən bölmə tələblərinə cavab verən qeyri-mənfi ədədləri saymağınız istənilir. Məsələn, əgər siz 2 rəqəmdən ibarət olan və 6-ya bölünən, lakin 5-ə bölünməyən ədədləri saymaq istəyirsinizsə, bu tələblərə cavab verən ədədlər bunlardır: 06, 12, 18, 24, 36, 42, 48, 54, 66, 72, 78, 84 və 96.
Qeyd edək ki, sıfır hər hansı müsbət ədədə bölünür (üçüncü nümunə test halına baxın).
Beləliklə, siz bu tapşırığı həll etmək üçün bir proqram yazmağa qərar verdiniz, çünki N həqiqətən böyük ola bilər.
Proqramınız bir və ya daha çox test halında yoxlanılacaq. Girişin ilk sətri test hallarının sayı olan tək bir tam ədəd T olacaq (1 ≤ T ≤ 1000). Ardınca T sətir gəlir, hər sətir bir test halını təmsil edir və saymalı olduğunuz ədədlərin uzunluğu olan bir tam ədəd N (1 ≤ N ≤ 10^18) və sonra bir boşluq və 6 rəqəmli bir sətir (hər rəqəm '0', '1' və ya '2'dir) ibarətdir. i-ci rəqəm (ən soldakı rəqəm rəqəm nömrəsi 1-dir) '0'-dırsa, ədədlər i-yə bölünməməlidir, '1'-dirsə, ədədlər i-yə bölünməlidir, '2'-dirsə, ədədlər bölünə və ya bölünməyə bilər.
Hər test halı üçün, yuxarıda təsvir edilən ədədlərin sayını tək bir sətirdə çap edin. Nəticə çox böyük ola biləcəyi üçün, onu 1000000007 (10^9 + 7) modulu ilə çap edin.
Nümunə 1