The Sultan of Sylvania loves throwing parties, because that gives him a reason to decorate the palace.He particularly likes decorations called streamers made up of diffrent beads strung together on a string and hung from the ceiling. Now, like most Sultans, he is very particular about everything, including these strung decorations. Specifically, he only likes certain combinations of beads to be used on the streamers. For example, if there are four diffrent types of beads - A, B, C and D - the Sultan might say "It pleases his highness that only the combinations ABB, BCA, BCD, CAB, CDD and DDA appear in the streamers at tonight's party". This, needless to say, puts a severe limit on the number of diffrent streamers possible. For example, if the length of the streamers was 5, then the only possible streams of beads would be BCABB and BCDDA (strings such as ABBCA could not be used because BBC is not an approved combination). Since the Sultan likes variety, it is important to know the total number of streamers possible, given a length and the current bead combinations which tickle the Sultan's fancy.