CaptureFish

There are N fish and N+1 buoys in a small pond. Mr. Jeipouju wants to capture some of the fish.

In this problem, regard the pond as a 2-dimensional Cartesian plane (as seen from above). Each fish and each buoy is a point on the plane. The buoys are lined up on x axis and numbered 0 to N from left to right. There is exactly one fish between each two neighboring buoys. The fish are numbered 0 to N-1 from left to right. For the purpose of this problem we will assume that the fish are staying on their spots without any movement. The exact coordinates of the fish and the buoys do not matter. See the following image for clarity.

You are given a String fish with N characters. Each character of fish is either letter 'O' or 'X' or '*'. If fish[i] is 'O', it represents that he must capture fish i. If fish[i] is 'X', he must not capture fish i. If fish[i] is '*', he does not care whether he capture fish i or not.

To capture the fish, Mr. Jeipouju wants to set up a net in the pond so that the net will separate the caught fishes from the uncaught ones. From above, the net must be a closed curve in our plane. Furthermore, this closed curve must satisfy the following conditions:

• The net is not allowed to pass through any of the fish.
• The net is not allowed to touch or intersect itself.
• The net may only cross the x axis at points that contain the buoys. The net is not allowed to touch the x axis without crossing it.
• The net must cross the x axis at least twice.
• The fish Mr. Jeipouju wants to capture and the fish he wants not to capture must be separated by the net. That is, either all fish marked with 'X' are to be inside the net and all fish marked with 'O' outside, or vice versa. The fish marked '*' may be anywhere, possibly some of them inside and some outside the net.

The following image shows some examples of valid and invalid net placements: 4 nets to the left are valid and 5 nets to the right are invalid.

A net can be encoded into a sequence using the following algorithm:

• Start anywhere on the net, but not on a buoy.
• Walk along the net until you reach your starting point again.
• During the walk, each time you encounter a buoy, write down its number and the halfplane in which you are moving away from the x axis. (The halfplane is "+" if after visiting the buoy your y coordinate is positive and "-" if it is negative.)

In this way you will obtain some sequence (buoy1,side1,...,buoyK,sideK). Two nets are considered the same if they can be encoded to the same sequence.

Mr. Jeipouju wants to know whether the number of different nets is odd or even. Your method must return the number of different nets, modulo 2.