Problem in short: Given a positive integer N, find the number of binary strings of length N which are not periodic. Report the answer modulo M. The non-periodic strings of length 3 are 001, 010, 011, 100, 101, and 110. N <= 150,000.

Indian National Olympiad in Informatics (INOI) is round 2 out of 3 (i.e. intermediate) for selection into Indian IOI team.