Counting powers of words in monoids

For a monoid MM with presentation M=〈a1,…,ar|w1=w2,…,w2s−1=w2s〉M=〈a1,…,ar|w1=w2,…,w2s−1=w2s〉, we count the number of words equivalent to w1n,n∈N, where equivalent means under the transitive closure of the relation generated by replacing an occurrence of w2i−1w2i−1 by w2iw2i or vice versa (for any ii). Many interesting sequences are obtained in this way including the Fibonacci numbers.