Counting Bad Streets With Tiling Cover Constraints

You are given a street represented as a string of N lowercase English letters. The city government sometimes replaces the tiles on the street. However, due to high demand for lettered tiles, there are only M types of tiles available. The i-th tile type is a string of length \(L_i\) (its letters given consecutively). A tile cannot be rotated or broken into pieces, and it can only be placed on a contiguous substring of the street if the letters on that substring exactly match the tile pattern.

Tiles are allowed to overlap and you may use any tile type arbitrarily many times. A street is considered good if there exists a collection (one or more placements) of tiles such that every letter position of the street is covered by at least one tile. Otherwise, the street is considered bad.

Your task is to count the number of bad streets among all \(26^N\) possible streets of length \(N\). (Note that a street is specified solely by its sequence of letters.)

Input constraints: For the purpose of this problem, you may assume that \(N\) and the lengths of the tiles are small enough so that a brute‐force solution that iterates over all \(26^N\) possible streets will run in reasonable time.

Problem Formalization

Given two positive integers \(N\) and \(M\) and tile patterns \(T_1, T_2, \dots, T_M\) (each \(T_i\) is a string of lowercase letters of length \(L_i\)), a street string \(S\) of length \(N\) is good if there exists a set of indices and corresponding tile placements such that for every position \(i\) (with \(0 \le i < N\)), there is some tile \(T_j\) placed at position \(p\) (where \(0 \le p \le N - L_j\)) satisfying:

[ S[p..p+L_j-1] = T_j \quad\text{and}\quad p \le i \le p+L_j-1. ]

If no such collection of placements exists to cover every position, then \(S\) is bad. Count the number of bad streets.

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space.

Then follow \(M\) lines, each containing a non‐empty string representing a tile pattern.

Example:

3 1
ab

outputFormat

Output a single integer: the number of bad streets among all possible \(26^N\) streets.

sample

3 1
ab

17576