CF314E.Sereja and Squares

Sereja painted n points on the plane, point number i (1 ≤ i ≤ n) has coordinates (i, 0). Then Sereja marked each point with a small or large English letter. Sereja don't like letter "x", so he didn't use it to mark points. Sereja thinks that the points are marked beautifully if the following conditions holds:

• all points can be divided into pairs so that each point will belong to exactly one pair;
• in each pair the point with the lesser abscissa will be marked with a small English letter and the point with the larger abscissa will be marked with the same large English letter;
• if we built a square on each pair, the pair's points will be the square's opposite points and the segment between them will be the square's diagonal, then among the resulting squares there won't be any intersecting or touching ones.

Little Petya erased some small and all large letters marking the points. Now Sereja wonders how many ways are there to return the removed letters so that the points were marked beautifully.

Sereja 在平面上画了 $n$ 个点，其中第 $i$ 个点（$1 \le i \le n$）的坐标为 $(i, 0)$。接着，Sereja 用小写或大写的英文字母标记了每个点。Sereja 不喜欢字母 “x”，因此他没有使用该字母来标记任何点。Sereja 认为点的标记是“优美的”，当且仅当满足以下条件：

• 所有点可以被划分为若干对，使得每个点恰好属于其中一对；
• 在每一对中，横坐标较小的点用一个小写英文字母标记，横坐标较大的点则用相同字母的大写形式标记；
• 若对每一对点以它们为正方形的一组对顶点、并以两点间的线段作为该正方形的对角线构造一个正方形，则所有这样得到的正方形之间互不相交且互不接触。

小 Petya 擦除了部分小写字母以及全部大写字母。现在 Sereja 想知道：有多少种方式将被擦除的字母恢复，使得点的标记变得“优美”？

The first line contains integer n the number of points (1 ≤ n ≤ 105). The second line contains a sequence consisting of n small English letters and question marks — the sequence of letters, that mark points, in order of increasing x-coordinate of points. Question marks denote the points without letters (Petya erased them). It is guaranteed that the input string doesn't contain letter "x".

第一行包含一个整数 $n$，表示点的数量（$1 \leq n \leq 10^5$）。第二行包含一个由 $n$ 个小写英文字母和问号组成的字符串——该字符串按点的 $x$ 坐标递增顺序给出各点所标记的字母。问号表示没有字母的点（Petya 已将其擦除）。保证输入字符串中不包含字母 “x”。

In a single line print the answer to the problem modulo 4294967296. If there is no way to return the removed letters, print number 0.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

在一行中输出该问题的答案对 4294967296 取模的结果。如果不存在恢复被删除字母的方法，则输出数字 0。

请注意，在 C++ 中不要使用 %lld 说明符来读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。