Sətir

Bir sıra var ki, üzərində tam olaraq N rəqəmdən ibarət natural ədəd yazıla bilər. Bu sıra üzərində aşağıdakı əməliyyatı yerinə yetirmək olar: ədədin istənilən iki ardıcıl rəqəmi arasında kəsik aparmaq, alınan iki hissəni çevirmədən yerlərini dəyişmək və yenidən birləşdirmək. Sıra "gözəl" hesab olunur, əgər bu əməliyyatdan sonra birləşdirilmiş sırada eyni ədəd alınarsa. Məsələn, 5656 ədədli sıra gözəldir, amma 5665 deyil. Sıra üzərində yazıldıqda onu gözəl edən müxtəlif ədədlərin sayını tapmaq lazımdır.

Giriş verilənləri

Proqram bir tam ədədi oxuyur: sıranın uzunluğu N. 1 ≤ N ≤ 1 000 007.

Çıxış verilənləri

Sıra "gözəl" edən N-rəqəmli ədədlərin sayını 1 000 007 modulunda çıxışa vermək lazımdır.

Nümunələr