Problema B - Para Cima e Para Baixo

Acabaste de subscrever um novo serviço que te permite ter um número de telefone à tua escolha. Como sempre foste um apaixonado pela matemática e por sequências interessantes de números, decidiste escolher um número que apresenta características muito próprias.

Estás interessado em escolher um número onde dois dígitos consecutivos nunca podem ser iguais, e onde os dígitos vão "para cima e para baixo", isto é, quando um dígito é mais pequeno que o dígito anterior, o dígito seguinte deve ser maior que o actual. Do mesmo modo, quando um dígito é maior que o dígito anterior, o dígito seguinte deve ser menor que o actual. Por outras palavras, o número não pode apresentar nenhuma subsequência crescente ou decrescente de 3 dígitos consecutivos.

Exemplificando, os seguintes números que apresentam esta propriedade:

143502, 09080706, 91827, 243 ou 7698901.

Quando te ias preparar para escolher, puseste-te a pensar em quantos números com esta propriedade existem. Mais do que isso, se alguns dígitos estiverem já preenchidos (queres incluir os teus números favoritos), de quantas maneiras diferentes podes preencher os dígitos que faltam de modo a que o número fique "para cima e para baixo", isto é, com as propriedades atrás descritas?

Considera por exemplo o seguinte caso, onde um algarismo de 0 a 9 representa um dígito já fixo e um ponto de interrogação indica um dígito ainda por preencher:

912??7

Neste caso, existem exactamente 4 maneiras de preencher os ? de modo a que o número apresente as propriedades desejadas:

912097, 912087, 912197, 912187.

Interessado em algoritmos como és, resolveste criar um programa para resolver o caso geral desta pergunta.

O Problema

Dado um número de telefone com D dígitos, onde alguns dígitos já estão fixos (têm um algarismo já definido) e outros estão por preencher, a tua tarefa é dizer de quantas maneiras M se podem preencher as posições em aberto de modo a que o número seja "para cima e para baixo", ou seja, não apresente dois dígitos consecutivos iguais, a seguir um par de dígitos decrescente apresente um dígito maior que o anterior e a seguir um par de dígitos crescente apresente um dígito menor que o anterior (tal como anteriormente foi descrito).

Input

Na primeira linha do input vem um número inteiro D indicando o número de dígitos a considerar. Segue-se uma linha contendo exactamente D caracteres. Cada um destes caracteres pode ser um algarismo entre zero e nove, indicando um dígito já fixo, ou um ponto de interrogação ('?'), indicando um dígito ainda por preencher. Existe sempre pelo menos um ponto de interrogação.

Output

O output deve ser constituído por uma única linha contendo um número inteiro M, indicando o número de maneiras diferentes com as quais se pode preencher as posições marcadas com ponto de interrogação de tal modo que o número fique "para cima e para baixo", tal como foi atrás descrito.

Para preencher as posições podes usar algarismos entre zero e nove (inclusive).

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 50% dos pontos, acontece sempre que D<10.

Exemplo de Input 1

6
912??7

Exemplo de Output 1

4

Exemplo de Input 2

5
9?9?9

Exemplo de Output 2

81