Во една замислена држава, секој граѓанин добива свој N-цифрен матичен број (матичните броеви може да почнуваат и со една или повеќе нули). Сепак, од религиозни или технички причини, постојат одреден број на правила кои дефинираат кои матични броеви се валидни:

    - Матичните броеви се составени од N цифри (0-9)

    - Матичните броеви не смеат да бидат палиндроми. Палиндром е текстуална низа која се чита идентично и од почеток и од крај, на пример 12321, 11111, 1551, 0001000, итн.

    - Матичните броеви не смеат да имаат одредени префикси (дадени како влезен податок) – т.е. матичен број не може да почнува со одредена група на цифри. На пример, можеби матичните броеви не можат да почнуваат со 070 за граѓаните да не се бунат што им е матичен број а што телефонски број, итн.

Напишете програма која ќе го определи бројот на валидни матични броеви.

Влез

Во првиот ред се запишани два цели броеви N и P (1 <= N <= 12, 0 <= P <= 30), кои го означуваат бројот на цифри од кои се составени матичните броеви, и бројот на забранети префикси, соодветно.

Во секој од следните P редови е даден по еден различен забранет префикс, составен од најмалку една и најмногу N цифри.

Забелешка: Во тест случаи кои носат најмалку 21% од поените, бројот на цифри ќе биде N <= 7.
Во други тест случаи кои носат најмалку 12% од поените, нема да има забранети префикси (P=0).

Излез

Отпечатете го бараниот број на валидни матични броеви.

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

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

Примери

влез
2 11
1
2
3
4
5
6
7
8
9
05
95

излез
8

влез
5 9
0
44
79
1
2
9
7
8315
65555

излез
48499

Објаснување за првиот пример: Матичните броеви се составени од N=2 цифри, и има 11 забранети префикси (1, 2, 3, 4, 5, 6, 7, 8, 9, 05, 95). Валидни матични броеви се: 01, 02, 03, 04, 06, 07, 08 и 09. Забележете, на пример, дека не се валидни броевите 31, 56 и 05 (и други) бидејќи започнуваат со забранет префикс, како и бројот 00 бидејќи е палиндром.