Many of my friends asked this interesting OA problem to me:

Given an array of strings $$$A$$$ of size $$$N$$$ and two integers $$$B$$$ and $$$C$$$.

Let $$$D$$$ be the number of strings of length $$$C$$$ that contains exactly $$$B$$$ of the strings in $$$A$$$ as substring.

Return $$$D$$$ mod $$$1e^9+9$$$.

Constraints $$$1 \le N \le 6$$$ $$$1 \le |A[i]| \le 50$$$ All the $$$N$$$ strings are distinct $$$0 \le B \le N$$$ $$$1 \le C \le 50.$$$