Shuffling Along

One way to mix a deck of cards is the perfect shuffle. A perfect shuffle splits the deck into two exact halves, then interleaves the two halves one card at a time.

Take the eight card deck ABCDEFGH, where A is the top card. Splitting it into ABCD and EFGH and interleaving them gives AEBFCGDH. The card that started on top, A, is still on top. This shuffle is called an out-shuffle. Starting instead with the first card of the second half gives EAFBGCHD, which is called an in-shuffle.

Unlike ordinary shuffling, a perfect shuffle produces only a small number of orderings. Repeating the out-shuffle on the eight card deck gives ABCDEFGH, AEBFCGDH, ACEGBDFH, ABCDEFGH, so the deck is back in its original order after 3 shuffles. Repeating the in-shuffle on the same deck takes 6 shuffles. A standard 52 card deck is back in its original order after 8 out-shuffles.

A perfect shuffle also works on a deck with an odd number of cards, but the split changes. For an out-shuffle the first half holds one more card than the second half, and for an in-shuffle it is the other way around. An out-shuffle on ABCDE gives ADBEC, and an in-shuffle on ABCDE gives CADBE.

Given the number of cards and the type of shuffle, find how many times the same shuffle must be repeated before the deck is back in its original order.

The first line contains an integer $n$ ($1 \le n \le 1000$), the number of cards, and a string giving the type of shuffle, separated by a space. The string is out for an out-shuffle and in for an in-shuffle.

Print the number of shuffles needed to bring the deck back to its original order.