DUGDUG - DUGDUG

Dug Dug is a sweet and cute girl who just loves to eat sweet and chocolates but only those which I used to gift her. One day I just said that "DUG DUG you are sweet and also like sweet". I will give you as many sweets as you want but you have to tell me the number of ways you can exchange the words in the sentence such that the sentence is not changed. Note that you can exchange one or more pair of words in the sentence simultaneously but all those pairs should be of different words. Dug Dug was confused. She got angry and said if you want to give the sweet then give otherwise go from here. I said "I i will, i i i will give". She got the chocolates but you will not get it easily.

Your task is to find out the number of ways words in a sentence can be exchanged without changing the sentence. Note - one or more pair of words in the sentence can be exchanged simultaneously but all those pairs should be of different words.

Input

Input will consists of several lines each containing a sentence consisting of not more than 5000 characters.

Output

For each line of input out a single integer denoting the number of ways in which words in a sentence can be exchanged without changing the sentence.

Example

Input:
DUG DUG you are sweet and also like sweet
I i will, i i i will give
Ok done you will get what you want
Done !!!!!!!!

Output: 3
13
1
0

Explanation:

For the first sentence "DUG DUG you are sweet and also like sweet" there are three ways -
1) You can change the first "DUG" with second "DUG"
2) You can change the first "sweet" with second "sweet"
3) You can change the first "DUG" with second "DUG" and first "sweet" with second "sweet".


Added by:Min2
Date:2012-02-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2020-01-19 09:07:13
The second sample has 4x "i" and 2x "will". If we denote i's with 1, 2, 3, 4 then ways to swap them are 12, 13, 14, 23, 24, 34 and simultaneously (12, 34), (13, 24), (14, 23). For each of these 9 ways one can also add simultaneous swapping of "will" 's. With 1 way of swapping "will" we get 19 ways. Can anyone explain why the result is 13 then?

Edit: (12, 34) etc doesn't count; statement is poorly written. All pairs swapped simultaneously must be distinct.

Last edit: 2020-01-19 09:15:26
2013-05-07 16:40:02 Govind Lahoti
time limit too strict for python
2012-12-25 18:19:38 (Tjandra Satria Gunawan)(曾毅昆)
@Robert Gerbicz: Thanks :-)
2012-12-25 14:26:02 Robert Gerbicz
Be careful, here word is a sequence of one ore more nonspace charcters, so for example 6a7!=&@v is also a word.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.