Busy Typing

Problem Statement

Busy Typing Problem Description Mike is a programmer. When he is coding he tries to type the code as fast as possible. Sometimes he tries to write 2 consecutive letters of a string at the same instance of time but that can cause problems sometimes. Like if the word is "range" and he tries to write the 'g' and 'e' at the same time instance then two words can be produced "range" and "raneg" i.e. the positions of consecutive letters can be swapped if 2 letters are typed at the same instance. He wants to type a given string S of lowercase English alphabets of length N. If Mike types i th and (i+1) th character at the same instance then he cannot type (i+1) th and (i+2) th character at the same instance for all valid i. It is not always necessary that he types 2 characters at a time. He can type 1 character at a time too. 1-based indexing is used. Task: Determine how many different strings can be produced because of his busy typing. As this number could be large, print it modulo 10 9 + 7. E