Kira, is dreaming of building a new world, where all expressions will be special sequences. All these sequences consists of characters 'A','a','B','b','C','c'.

He devised the following rules:

An empty sequence is a valid sequence.

If Sequence1 is a special sequence, then so will be 'A' + Sequence1 + 'a', 'B' + Sequence1 + 'b', 'C' + Sequence1 + 'c'.
Example, let Sequence1="", then Aa, Bb, Cc are also valid sequences.

If Sequence1 and Sequence2 are valid, then so is the sequence formed by concatenation of Sequence1 and Sequence2.

L (Kira's rival), has now replaced some characters with garbage from Kira's some of the favourite special sequences. Kira thinks he can add characters on his own to make then special again. You have to tell him number of special sequences that can be formed by replacing garbage characters with valid characters.

Input:

The first line contains N (it will be always even), the length of the sequence. Next line contains the string. Garbage characters in strings are denoted by '?'.

Output:

Print in one line the number of Special Sequences that can be formed by replacing '?' with valid characters.

Since this number could be huge, print this number modulo 100000.

Constraints:

2 ≤ N ≤ 200

SAMPLE INPUT
10
A?AC?ac?b?

SAMPLE OUTPUT
3

Explanation

The 3 special sequences are:

ABACAacaba

AaACAaCBbb

ACACcacBba

见题面

见题面