Hello guys! Recently I took part in Reply Challenges Coding Contest and there was an interesting counting problem I couldn't find its solution. It goes like this: You are given N <= 10^9 and M <= 1100 and a binary string B of length M. Count how many binary strings A of length N exist such that A does not contain B as a substring. Output the answer mod 10^9 + 7. During the contest we had a 4 min span of running an input and giving its answer, so not so fast solutions could work, however I would prefer the fastest solution to this, but any idea is welcomed by me. Original statement: https://challenges.reply.com/tamtamy/file/download-95022.action Thank you!