Derangement

Time Limit: 7000/7000 MS (Java/Others)

Memory Limit: 65535/102400 K (Java/Others)

Description

A derangement is a permutation such that none of the elements appear in their original position. For example, [5, 4, 1, 2, 3] is a derangement of [1, 2, 3, 4, 5]. Subtracting the original permutation from the derangement, we get the derangement difference [4, 2, -2, -2, -2], where none of its elements is zero. Taking the signs of these differences, we get the derangement sign [+, +, -, -, -]. Now given a derangement sign, how many derangements are there satisfying the given derangement sign?

Input

There are multiple test cases. Process to the End of File.
Each test case is a line of derangements sign whose length is between 1 and 20, inclusively.

Output

For each test case, output the number of derangements.

Sample Input

+- ++---

Sample Output

1 13

Hint

zhuyuanchen520

Source

2013 Multi-University Training Contest 9

提交代码