Zəncir#3675
Zəncir halqadan ibarətdir və hər biri rəngdən birinə boyanmışdır. İki belə zənciri nəzərdən keçirək. Hər biri üçün kənar halqalardan birini seçək və ondan başlayaraq, onun tərkibində olan bütün halqaların rənglərini ardıcıllıqla yazacağıq. Əgər bu zəncirlərdən eyni rəng ardıcıllıqlarını əldə etmək mümkündürsə, onları eyni hesab edəcəyik.
Sizdən tələb olunan, fərqli zəncirlərin sayını tapmaqdır.
Giriş faylında və (1 \leq N \leq 10^9, 1 \leq K \leq 10^9) ədədləri verilmişdir.
halqadan ibarət və hər biri rəngdən birinə boyanmış fərqli zəncirlərin sayını çıxışa yazın. Əgər cavab -u keçərsə, axtarılan ədədin son doqquz rəqəmini çıxışa yazın.
Nümunə 1