有足够多的卡片，上面分别写着从 $1$ 到 $34$ 的整数。将其中的几张排成一行，按顺序写下上面的数字。例如，卡片如下排列时，按顺序写下数字得到 $27123$。
27 | 1 | 23
后来，想根据写下的数字重新排列卡片时，发现可能有多种排列方法。
例如，对于 $27123$，有如下六种不同的方法。
2 | 7 | 1 | 2 | 3 27 | 1 | 2 | 3 2 | 7 | 12 | 3 2 | 7 | 1 | 23 27 | 12 | 3 27 | 1 | 23
给定按顺序写下的卡片上的数字，要像上面这样反过来找出卡片的排列。请编写程序，求出所有可能的卡片排列的数量。
输入格式
第一行给出按顺序写下的卡片上的数字，由不超过 $40$ 个数字字符组成。
输出格式
输出可能的卡片排列的数量。
样例
输入格式 1
27123
输出格式 1
6
输入格式 2
77777777777777777777
输出格式 2
1