Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3108
Last Digit

Time Limit: 2 Seconds      Memory Limit: 32768 KB

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


Source: The 2007 ACM Mexico and Central America Programming Contest
Submit    Status