Sereja and Squares

题目描述： Sereja在平面上画了n个点，第i点(1<=i<=n)坐标为(i,0)。然后Seraja在每个点上标记了一个大写或小写的英文字母。Seraja不喜欢字母'x'，所以她没有用'x'标记任何点。Seraja认为，当标记方式满足以下条件时，这些点就被“美丽地”标记了： 1.所有点能够被分成若干点对，每个点在且仅在一个点对中； 2.在每个点对中，横坐标较小的点被小写字母标记，横坐标较大的点被同一字母的大写形式标记； 3.以每组点对连线为对角线作正方形，所有作出的正方形的边没有交点且没有顶点重合； 小Petya擦去了标记在点上的一些小写或大写字母。现在Seraja想知道有几种方式标记被擦去字母的点，能够使所有点被“美丽地”标记了。 输入格式： 第一行包含一个整数n(1<=n<=10^5)，表示点的个数。 第二行包含一个由n个小写字母和问号组成的字符串，以横坐标升序给出，问号表示被小Petya擦去的点。输入保证不含'x'。 输出格式： 一行，输出答案对4294967296取模后的结果。如果没有任何一种方式能够使所有点被“美丽地”标记了，输出0。 c++coder注意，请不要用格式控制符%lld读取64位长整形，使用cin或%I64d会更好 翻译提供者：zxyoi

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.

The first line contains integer $ n $ the number of points $ (1<=n<=10^{5}) $ . 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".

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.

4
a???

50

4
abc?

0

6
abc???

1