The number of permutation without repetition that has a string S is so big, but in this problem you just need to print the last nonzero digit of it.
Input
In each test case you have a string S (1 <= |S| <= 1000000), all characters in the string are lowercase.
Output
For each test case print the last nonzero digit.
Sample Input
aaba
aaabababababa
abbzazzazzalzalzzaaaaazlalzaazlalzla
w
Sample Output
4
7
8
1
Hints
For example for the first test case the permutation are:
aaab
aaba
abaa
baaa
