Description

DNA序列是一个只包含A、C、T和G的序列。分析DNA序列片段非常有用，若动物的DNA序列包含片段ATC，则意味着该动物可能患有遗传病。给定$m$个遗传病片段，求有多少种长度为$n$的DNA序列不包含这些片段。

Format

Input

第1行包含两个整数$m （0≤m ≤10）$和$n （1≤n ≤2×109）$。$m$ 是遗传病片段的数量，$n$是序列的长度。接下来的$M$ 行，每行都包含一个DNA遗传病片段（长度不大于$10$）。

Output

一个整数，不包含遗传病的DNA序列数$mod$ $100000$。

Samples

4 3
AT
AC
AG
AA

36

来源

POJ2778