Предраг, еден од македонските натпреварувачи по информатика, има сериозен проблем да ги запамети имињата на натпреварувачите кои доаѓаат на Интернационални Олимпијади по Информатика, а се од други држави (особено од Индија - поради должината на нивните имиња). Во задачата, ќе претпоставиме дека сите имиња се составени само од малите латинични букви (а до z), и не содржат други специјални знаци како цртичка, празно место, итн.

Ваша задача е да му помогнете на Предраг да пресмета колку различни имиња можат да се состават користејќи ги податоците кои што тој ги знае за одреден натпреварувач. Конкретно, Предраг ја знае должината на името N на натпреварувачот, и се сеќава на одредени делови од името на натпреварувачот, но не знае во кој редослед се тие наредени во неговото име (и дали, можеби, се препокриваат). Напишете програма која ќе пресмета колку имиња може да се состават почитувајќи ги овие податоци. Дополнително, доколку бројот е помал или еднаков на 30, отпечатете ги тие имиња за да може Предраг да почне да ги извикува имињата едно по едно, па кога натпреварувачот ќе се сврти, Предраг да знае кое е всушност точното име на натпреварувачот :).

На пример, нека Предраг знае дека името на натпреварувачот има должина 8, и дека некаде во името се наоѓаат деловите "hare" и "ndra". Тогаш, името на натпреварувачот е или "harendra" или "ndrahare". Од друга страна, доколку името на натпреварувачот има должина 5, и доколку Предраг знае дека во името се наоѓаат деловите "aabb" и "abbz", тогаш постои само едно можно име: "aabbz". Ако пак името на натпреварувачот има должина 5, и Предраг знае дека во името се наоѓа делот "aaaa", тогаш постојат 51 можност за име: "ааааа", "baaaa", "caaaa" ... "zaaaa", "aaaab", "aaaac" ... "aaaaz".

Влез

Во првиот ред се запишани два цели броја N (2 ≤ N ≤ 25) и O (0 ≤ O ≤ 9), кои ја означуваат должината на името (N) и бројот на делови од името (О) на кои се сеќава Предраг, соодветно.

Во секој од следните O редови е запишан по еден дел од името на натпреварувачот, не подолг од 10 знаци, и составен само од малите латинични букви 'a'-'z'.

Излез

Во првиот ред отпечатете го бројот на можни имиња. Доколку овој број не надминува 30, во следните редови отпечатете ги можните имиња (по едно име во секој ред). Имињата треба да се отпечатат во лексикографски редослед.

Тест случаите ќе бидат направени така што секогаш ќе постои барем едно можно име, и вкупниот број на можни имиња нема да надминува 10¹⁵.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
8 2
hare
ndra

излез
2
harendra
ndrahare

влез
3 0

излез
17576