Ноён Китаюта чамд Англи цагаан толгойн жижиг үсгүүдээс бүтсэн $s$ тэмдэгт мөр бэлэглэжээ. Чи энэ тэмдэгт мөрөнд яг нэг үсэг нэмэн палиндром үг үүсгэх ёстой. Палиндром үг гэдэг нь хойноос нь ч уншсан, урдаас нь ч уншсан адилхан байдаг тэмдэгт мөр юм. Жишээ нь "noon", "testset" ба "a" нар нь палиндром, харин "test" ба "kitayuta" нар нь биш юм.

Чи Англи цагаан толгойн дурын $n$ жижиг үсэг сонгон түүнийгээ $s$ тэмдэгт мөрийн хаа нэгтээ байрлуулна. $s$-ийн эхэнд эсвэл сүүлд байсан ч болно. Хэдий анхны тэмдэгт мөр палиндром байсан ч $n$ ширхэг үсэг нэмэх ёстой.

Ийм замаар үүсгэж болох Палиндромын тоог $10007$-д хуваасан үлдэгдлийг олно уу.

Оролт

Эхний мөрөнд тэмдэгт мөр $s$ ($1 ≤ |s| ≤ 200$) өгөгдөнө. $s$ тэмдэгт мөр Англи цагаан толгойн жижиг үсгүүдээс тогтоно.

Хоёрдахь мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 10^{9}$) байна.

Гаралт

Үүсгэж болох палиндромын тоог $10007$-д хуваасан үлдэгдлийг хэвлэнэ үү.

Эхний жишээнд "revive"-ийн ард "r" үсэг нэмэн "reviver" гэсэн палиндром үүсгэж чадна.

Хоёрдахь жишээнд дараах $28$ палиндромыг үүсгэж чадна: "adada", "adbda", ..., "adzda", "dadad", "ddadd".