Ethan Hunt's Mission#343
Ethan Hunt, the hero of the "Mission Impossible" series, is renowned for his skills as a saboteur. However, there was an instance when the CIA enlisted him to evaluate the reliability of their door codes. As depicted in popular films, CIA code locks are typically opened using a magnetic card. Let's assume this card holds a sequence of bits of length . When these bits are read, if they match the door code, the door unlocks. When asked how he would breach such a lock, Hunt suggested the following approach.
Imagine a long magnetic tape on which we record an arbitrary sequence of length (N \geq M), composed of s and s, with each bit having an equal probability of being or . We then pass this tape through the lock. If the lock code appears anywhere in this sequence, the lock will open. (Note: This scenario is set in a Hollywood movie, so the mismatch between the physical encoding of a continuous tape and a magnetic card is not a concern.)
The CIA's leadership decided to evaluate all lock codes for their resistance to Hunt's method.
The first line contains the number (1 \leq N \leq 60) — the length of the bit sequence recorded on the tape. The second line contains the lock code — a non-empty string of characters **"0"** and **"1"**, whose length does not exceed .
Output the probability that the lock code appears in a randomly generated sequence of bits of length . The probability should be presented as an irreducible fraction, with the numerator and denominator separated by the symbol **"/"**.
Example 1