Bir sətir təbii ədədi ifadə edən və dəqiq rəqəmdən ibarət olan bir sətiri təsvir edə bilər. Bu sətir üzərində aşağıdakı əməliyyatı yerinə yetirmək olar: sətiri istənilən iki ardıcıl rəqəm arasında kəsə, yaranan iki hissəni sıranı pozmadan yerlərini dəyişə və sonra birləşdirə bilərsiniz. Sətir, bu əməliyyatdan sonra hələ də eyni ədədi ifadə edirsə, gözəl adlanır. Məsələn, ədədi gözəldir, amma gözəl deyil. Sətirə gözəllik verən neçə müxtəlif -rəqəmli ədəd yazmaq olar?
Girişdə bir tam ədəd var: sətirin uzunluğu . 1 \leq N \leq 1\ 000\ 007.
Sətiri gözəl edən -rəqəmli ədədlərin sayını modulu üzrə çap edin.
Nümunə 1