

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
高橋くんは、暗証番号を忘れてしまいました。暗証番号は 0 から 9 までの数字のみからなる 4 桁の文字列で、0 から始まる場合もあります。
0 から 9 までの各数字について、高橋くんは以下のように記憶しています。彼の記憶は長さ 10 の文字列 S_0S_1 \ldots S_9 によって表されます。
- S_i が
o
のとき : 数字 i は暗証番号に確実に含まれていた。 - S_i が
x
のとき : 数字 i は暗証番号に確実に含まれていなかった。 - S_i が
?
のとき : 数字 i が暗証番号に含まれているか分からない。
高橋くんが忘れてしまった暗証番号としてあり得るものは何通りありますか?
制約
- S は
o
,x
,?
のみからなる長さ 10 の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
ooo???xxxx
出力例 1
108
例えば 0123
や 0021
などがあり得ます。
入力例 2
o?oo?oxoxo
出力例 2
0
あり得る暗証番号が存在しない、即ち答えが 0 通りになる場合もあります。
入力例 3
xxxxx?xxxo
出力例 3
15
Score : 300 points
Problem Statement
Takahashi has forgotten his PIN. The PIN is a four-digit string consisting of 0
, 1
, \ldots, 9
, and may begin with a 0
.
For each digit 0
through 9
, Takahashi remembers the following fact, represented by a 10-character string S_0S_1 \ldots S_9:
- if S_i is
o
: he is certain that the PIN contained the digit i; - if S_i is
x
: he is certain that the PIN did not contain the digit i; - if S_i is
?
: he is not sure whether the PIN contained the digit i.
How many strings are there that could be Takahashi's PIN?
Constraints
- S is a 10-character string consisting of
o
,x
, and?
.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
ooo???xxxx
Sample Output 1
108
Some of the possible PINs are 0123
and 0021
.
Sample Input 2
o?oo?oxoxo
Sample Output 2
0
There may be no possible PINs, in which case the answer is 0.
Sample Input 3
xxxxx?xxxo
Sample Output 3
15