身份识别码

题目描述

有一个四位的身份识别码（PIN），它由$0-9$的数字构成，允许存在前导$0$，现在给出一个长度为$10$的字符串$s_0s_1s_2...s_9$，表示每一种数字是否在身份识别码中出现，具体如下：

• 如果$s_i=$ o，表示PIN一定包含数字$i$
• 如果$s_i=$ x，表示PIN一定不包含数字$i$
• 如果$s_i=$ ？，表示PIN可能包含也可能不包含数字$i$

请你找出满足上述条件的PIN的数量。

输入格式

一行一个长度为$10$的字符串$S$，仅含有字符" o,x,? "。

输出格式

一行一个数，表示满足条件的PIN的数量。

样例 #1

样例输入 #1

ooo???xxxx

样例输出 #1

108

样例 #2

样例输入 #2

o?oo?oxoxo

样例输出 #2

0

提示

样例解释

样例1：0123和0021是满足条件的2种，一共108种，因为根据样例知道肯定有0,1,2，肯定没有6,7,8,9，3,4,5可有可无，则分类讨论：

? 1、有一个3或4或5时，方案数为$C(3,1)*A(4,4)$，即先从4,5,6这三个数中选一个数，设为x，然后0,1,2,x这四个数做全排列，分步相乘。

? 2、没有3,4,5时，有两个$0$时方案数为$A(3,3)*3$，即0,1,2先做全排列，然后0有3个位置可插入，同理可得有两个1或2时的方案数为$A(3,3)*2$ 和? $A(3,3)*1$，注意此时会和前面有重复了，所以插入位置数依次减少1个。

综上得方案数为$C(3,1)*A(4,4) +A(3,3)*3+A(3,3)*2+A(3,3)=24*3+18+12+6=108$。

求助