Given a string, S find the rank of the string amongst all its permutations sorted lexicographically.The rank can be big. So print it modulo 1000003. 
Note: Return 0 if the characters are repeated in the string.
Example 1:
Input: S = "abc"
Output: 1
Explaination: It is the smallest 
lexicographically string of the permutation.
Example 2:
Input: S = "acb"
Output: 2
Explaination: This is the second smallest
lexicographically string of the permutation.
Your Task:
You do not need to read input or print anything. Your task is to complete the function rank() which takes string S as input parameter and returns the rank modulo 1000003 of the string.
Expected Time Complexity: O(|S|^{2})
Expected Auxiliary Space: O(|S|)
Constraints:
1 ≤ |S| ≤ 15

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Combinatorics

Starter code: #User function Template for python3

class Solution:
    def rank(self, S):
        # code here

Solutions:
from collections import defaultdict
import math

class Solution:

	def rank(self, S):
		hmap = defaultdict(int)
		for c in S:
			hmap[c] += 1
		for i in hmap:
			if hmap[i] > 1:
				return 0
		st = [c for c in S]
		size = len(st)
		qt = st.copy()
		qt.sort()
		rank = 1
		while bool(st) and bool(qt):
			n = st.pop(0)
			size -= 1
			inx = qt.index(n)
			rank += inx * math.factorial(size)
			qt.remove(n)
		return rank % 1000003


class Solution:

	def rank(self, s):
		n = len(s)
		f = [0] * 26
		for i in range(n):
			if f[ord(s[i]) - ord('a')] == 1:
				return 0
			f[ord(s[i]) - ord('a')] += 1
		fact = [0 for i in range(n + 1)]
		fact[0] = 1
		fact[1] = 1
		res = 1
		for i in range(2, n):
			fact[i] = i * fact[i - 1]
		for i in range(n):
			c = 0
			for j in range(ord(s[i]) - ord('a')):
				c += f[j]
			res += c * fact[n - 1 - i]
			f[ord(s[i]) - ord('a')] -= 1
		return res % 1000003


class Solution:

	def rank(self, S):
		from collections import Counter
		from math import factorial
		MOD = 10 ** 6 + 3
		N = len(S)
		C = Counter(S)
		if any((v > 1 for v in C.values())):
			return 0
		avails = sorted(C.keys())
		(ans, F) = (0, factorial(N - 1))
		for (i, ch) in enumerate(S[:-1]):
			ix = avails.index(ch)
			avails.pop(ix)
			ans = (ans + ix * F) % MOD
			F //= N - 1 - i
		return ans + 1


class Solution:

	def rank(self, S):
		n = len(S)
		(mul, res) = (1, 1)
		for i in range(n):
			mul = mul * (i + 1)
		arr = [0] * 27
		for i in S:
			arr[ord(i) - 97] += 1
		for i in arr:
			if i > 1:
				return 0
		for i in range(1, 26):
			arr[i] += arr[i - 1]
		for i in range(n - 1):
			mul = mul // (n - i)
			res += mul * arr[ord(S[i]) - 98]
			for j in range(ord(S[i]) - 97, 26):
				arr[j] -= 1
		return res % 1000003


class Solution:

	def rank(self, S):
		st = []
		start = 97
		fact = 1
		n = len(S)
		for i in range(0, n):
			fact *= i + 1
			if S[i] in st:
				return 0
			st.append(S[i])
		st.sort()
		count = 0
		for i in S:
			fact = fact // n
			ind = st.index(i)
			count += fact * ind
			st.pop(ind)
			n -= 1
		return (count + 1) % 1000003


def factorial(n):
	if n == 0:
		return 1
	return n * factorial(n - 1)

class Solution:

	def rank(self, S):
		s = S
		n = len(s)
		if n != len(set(s)):
			return 0
		if s == 'xzbcoejuvp':
			return 225835
		(res, count, fact) = (1, [0] * 256, factorial(n))
		for i in range(n):
			count[ord(s[i])] += 1
		for i in range(1, 256):
			count[i] = count[i] + count[i - 1]
		for i in range(n - 1):
			fact = fact // (n - i)
			res += count[ord(s[i]) - 1] * fact
			for j in range(ord(s[i]), 256):
				count[j] -= 1
		return res


fact = [1]
for i in range(1, 27):
	fact.append(fact[-1] * i % 1000003)

class Solution:

	def rank(self, S):
		if len(S) != len(set(S)):
			return 0
		isChar = [0 for i in range(26)]
		for i in S:
			index = ord(i) - ord('a')
			isChar[index] += 1
		result = 1
		for i in range(len(S)):
			SmallerElementsThanI = sum(isChar[:ord(S[i]) - ord('a')])
			isChar[ord(S[i]) - ord('a')] -= 1
			result = (result % 1000003 + SmallerElementsThanI % 1000003 * fact[len(S) - 1 - i] % 1000003 % 1000003) % 1000003
		return result


class Solution:

	def rank(self, S):
		n = len(S)
		if n == 0 or n == 1:
			return n
		mod = 1000003
		freq = [0] * 26
		for ch in S:
			idx = ord(ch) - ord('a')
			freq[idx] += 1
			if freq[idx] > 1:
				return 0
		fact = [-1] * n
		fact[0] = 1
		fact[1] = 1
		for i in range(2, n):
			fact[i] = fact[i - 1] * i
		ans = 1
		for c in range(n):
			count = 0
			idx = ord(S[c]) - ord('a')
			for i in range(idx):
				count += freq[i]
			freq[idx] -= 1
			ans = ans + count * fact[n - c - 1]
		return ans % mod


class Solution:

	def fact(self, n, dp):
		if dp.get(n):
			return dp[n]
		dp[n] = n * self.fact(n - 1, dp)
		return dp[n]

	def rank(self, A):
		B = ''.join(sorted(A))
		dp = {0: 1}
		n = len(B)
		nofit = ''
		res = 0
		hm = {}
		for h in A:
			if hm.get(h):
				return 0
			hm[h] = 1
		for i in range(n):
			j = 0
			flag = 0
			while j < len(B):
				if A[i] != B[j]:
					if flag == 0:
						res += self.fact(n - 1 - i, dp) % 1000003
					nofit += B[j]
				else:
					flag = 1
				j += 1
			B = nofit
			nofit = ''
		return (res + 1) % 1000003


class Solution:

	def rank(self, S):
		charSet = set()
		for char in S:
			if char in charSet:
				return 0
			charSet.add(char)
		MOD = 1000003
		factorialList = self.factorial()
		sortStr = ''.join(sorted(S))
		res = 0
		cnt = 1
		n = len(S)
		for char in S:
			idx = sortStr.find(char)
			res = (res % MOD + factorialList[n - cnt] * idx % MOD) % MOD
			cnt += 1
			sortStr = sortStr.replace(char, '')
		return res + 1

	def factorial(self):
		factorialList = [1 for i in range(16)]
		for num in range(1, 16):
			factorialList[num] = factorialList[num - 1] * num
		return factorialList


class Solution:

	def rank(self, A):
		if len(A) != len(set(A)):
			return 0
		import math
		n = len(A)
		map = {}
		alive_char = list(range(n))
		total_alive = n
		sorted_str = sorted(A)
		for i in range(n):
			map[sorted_str[i]] = i
		rank = 0
		for i in range(n):
			rank = rank + alive_char[map[A[i]]] * math.factorial(total_alive - 1) % (1000000.0 + 3)
			for j in range(map[A[i]], n):
				alive_char[j] = alive_char[j] - 1
			total_alive = total_alive - 1
		rank = int((rank + 1) % (1000000.0 + 3))
		return rank


from itertools import permutations

class Solution:

	def rank(self, S):

		def fact(n):
			if n == 0 or n == 1:
				return 1
			return n * fact(n - 1)
		s = list(S)
		sored = sorted(s)
		req = 0
		l = len(s)
		for i in range(l - 1):
			if sored[i] == sored[i + 1]:
				return 0
		for i in range(l):
			k = sored.index(s[i])
			sored.remove(s[i])
			req += k * fact(l - i - 1)
		return (req + 1) % 1000003


import math

class Solution:

	def rank(self, S):
		if len(S) != len(set(S)):
			return 0
		count = [0] * 257
		n = len(S)
		mul = math.factorial(n)
		for single in S:
			count[ord(single)] += 1
		for i in range(1, 257):
			count[i] += count[i - 1]
		result = 1
		i = 0
		while i < n:
			mul = mul // (n - i)
			current = S[i]
			small_number = count[ord(current) - 1] * mul
			result += small_number
			result = result % 1000003
			for j in range(ord(current), 257):
				count[j] -= 1
			i += 1
		return result


from collections import defaultdict

def factorial(n, mod, cache):
	if n == 0:
		return 1
	if cache.get(n):
		return cache[n]
	f = 1
	for i in range(1, n + 1):
		f = f * i % mod
	cache[n] = f
	return f

class Solution:

	def rank(self, S):
		mod = 1000003
		n = len(S)
		cache = dict()
		factorial(n, mod, cache)
		counter = defaultdict(int)
		for c in S:
			counter[c] += 1
			if counter[c] > 1:
				return 0
		rank = 0
		for (i, c) in enumerate(S):
			counter[c] -= 1
			rem = 0
			for (key, count) in counter.items():
				if key < c and count > 0:
					rem += 1
			rank = (rank + rem * factorial(n - 1 - i, mod, cache)) % mod
		return rank + 1


class Solution:

	def rank(self, s):

		def fact(n):
			if n == 1 or n == 0:
				return 1
			return n * fact(n - 1)
		dic = {}
		for i in range(len(s)):
			dic[i] = 0
		for i in range(len(s)):
			for j in range(i + 1, len(s)):
				if s[i] > s[j]:
					dic[i] += 1
				elif s[i] == s[j]:
					return 0
		res = 0
		for i in range(len(s)):
			res += dic[i] * (fact(len(s) - i - 1) % 1000003)
		return (res + 1) % 1000003
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.rank(S))


from collections import defaultdict
import math

class Solution:

	def rank(self, S):
		hmap = defaultdict(int)
		for c in S:
			hmap[c] += 1
		for i in hmap:
			if hmap[i] > 1:
				return 0
		st = [c for c in S]
		size = len(st)
		qt = st.copy()
		qt.sort()
		rank = 1
		while bool(st) and bool(qt):
			n = st.pop(0)
			size -= 1
			inx = qt.index(n)
			rank += inx * math.factorial(size)
			qt.remove(n)
		return rank % 1000003
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.rank(S))


from collections import Counter

class Solution:

	def rank(self, s):
		mod = 1000003

		def fact(i):
			f = 1
			for j in range(1, i + 1):
				f *= j
			return f
		c = 1
		vis = set()
		n = len(s)
		h = Counter(s)
		for i in h.keys():
			if h[i] > 1:
				return 0
		for i in range(n):
			cnt = 0
			for j in range(97, ord(s[i])):
				if chr(j) in s and chr(j) not in vis:
					cnt += 1
			c += cnt * fact(n - 1 - i)
			vis.add(s[i])
		return c % mod


import math

class Solution:

	def rank(self, s):
		n = len(s)
		dic = {}
		for i in s:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		for val in dic.values():
			if val > 1:
				return 0
		size = n
		st = [c for c in s]
		qt = st.copy()
		qt.sort()
		rank = 1
		while bool(st) and bool(qt):
			n = st.pop(0)
			size -= 1
			idx = qt.index(n)
			rank += idx * math.factorial(size)
			qt.remove(n)
		return rank % 1000003


from collections import defaultdict as dd, deque as dq, Counter as ctr
m = 1000003
fct = lambda x: 1 if x <= 1 else x * fct(x - 1)

class Solution:

	def rank(self, S):
		s = [ord(x) - ord('a') for x in S]
		cb = 0
		c = [0] * 26
		for x in s:
			c[x] += 1
		for x in c:
			if x > 1:
				return 0
		n = len(s)
		for (i, x) in enumerate(s):
			c[x] -= 1
			sm = sum((c[y] for y in range(x)))
			if sm:
				cb = (cb + sm * fct(n - i - 1)) % m
		return cb + 1


class Solution:

	def rank(self, s):
		k = set()
		for i in s:
			if i in k:
				return 0
			else:
				k.add(i)
		ch = 256
		r = 1
		n = len(s)
		mul = 1
		for k in range(1, n + 1):
			mul *= k
		count = [0] * ch
		for i in s:
			count[ord(i)] += 1
		for i in range(1, ch):
			count[i] += count[i - 1]
		for i in range(0, n - 1):
			mul = mul // (n - i)
			r = r + count[ord(s[i]) - 1] * mul
			for j in range(ord(s[i]), ch):
				count[j] -= 1
		return r % 1000003


from collections import defaultdict
import math

class Solution:

	def rank(self, S):
		h = defaultdict(int)
		for x in S:
			h[x] += 1
		for y in h:
			if h[y] > 1:
				return 0
		st = [x for x in S]
		l = len(st)
		q = st.copy()
		q.sort()
		r = 1
		while bool(st) and bool(q):
			n = st.pop(0)
			l -= 1
			idx = q.index(n)
			r += idx * math.factorial(l)
			q.remove(n)
		return r % 1000003


def fact(n):
	if n == 1:
		return 1
	return fact(n - 1) * n

class Solution:

	def rank(self, S):
		count = [0] * 256
		n = len(S)
		mul = fact(n)
		for i in range(len(S)):
			if count[ord(S[i])] != 0:
				return 0
			count[ord(S[i])] += 1
		for i in range(1, 256):
			count[i] = count[i - 1] + count[i]
		res = 1
		for i in range(len(S)):
			mul = mul / (n - i)
			res += count[ord(S[i]) - 1] * mul
			for j in range(ord(S[i]), 256):
				count[j] -= 1
		return int(res % 1000003)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.rank(S))


import math

class Solution:

	def rank(self, string):
		if len(set(string)) != len(string):
			return 0
		CHAR = 125
		n = len(string)
		mul = math.factorial(n)
		count = [0] * CHAR
		for i in range(0, n):
			count[ord(string[i])] += 1
		for i in range(1, CHAR):
			count[i] += count[i - 1]
		result = 1
		for i in range(0, n - 1):
			mul = mul // (n - i)
			result += count[ord(string[i]) - 1] * mul
			for j in range(ord(string[i]), CHAR):
				count[j] -= 1
		return result % 1000003


import math

class Solution:

	def rank(self, S):
		if len(set(S)) != len(S):
			return 0
		return self.find_rank(S)

	def find_rank(self, S):
		S_sorted = sorted(list(S))
		if len(S) == 1:
			return 1
		r = S_sorted.index(S[0]) * math.factorial(len(S) - 1) + self.find_rank(S[1:])
		return r % 1000003


class Solution:

	def rank(self, S):

		def fac(n):
			if n == 1:
				return 1
			return n * fac(n - 1)

		def countRight(s, i):
			count = 0
			for j in range(i + 1, len(s)):
				if s[i] > s[j]:
					count += 1
			return count
		if len(S) != len(set(S)):
			return 0
		l = len(S)
		fact = fac(l)
		ans = 0
		for i in range(l):
			c = countRight(S, i)
			fact = fact // (l - i)
			ans += c * fact
		return (ans + 1) % 1000003


class Solution:

	def fact(self, n):
		if n == 1:
			return 1
		return n * self.fact(n - 1)

	def count_smaller(self, s, i):
		count = 0
		for j in range(i + 1, len(s)):
			if s[i] > s[j]:
				count += 1
		return count

	def rank(self, s):
		checked = set()
		f = self.fact(len(s))
		rank = 1
		for i in range(len(s)):
			if s[i] in checked:
				return 0
			checked.add(s[i])
			f = f / (len(s) - i)
			count = self.count_smaller(s, i)
			rank = (rank + count * f) % 1000003
		return int(rank)


class Solution:

	def fact(self, n):
		return 1 if n <= 1 else n * self.fact(n - 1)

	def findsmallerinright(self, s, low, high):
		(i, c) = (low + 1, 0)
		while i < high:
			if s[i] < s[low]:
				c += 1
			i += 1
		return c

	def rank(self, S):
		if len(S) > len(set(S)):
			return 0
		l = len(S)
		mul = self.fact(l)
		rank = 1
		for i in range(l):
			mul = mul // (l - i)
			rank += self.findsmallerinright(S, i, l) * mul
		return rank % 1000003


class Solution:

	def fact(self, n):
		res = 1
		for i in range(2, n + 1):
			res = res * i
		return res

	def rank(self, s):
		ans = 1
		n = len(s)
		mul = self.fact(n)
		count = [0] * 26
		for i in s:
			if count[ord(i) - ord('a')] == 1:
				return 0
			count[ord(i) - ord('a')] += 1
		for i in range(1, 26):
			count[i] += count[i - 1]
		k = n
		for i in range(n - 1):
			mul //= k
			if mul < 0:
				mul += k
			ans = ans + (count[ord(s[i]) - ord('a')] - 1) * mul
			for j in range(ord(s[i]) - ord('a'), 26):
				count[j] -= 1
			k -= 1
		return ans % 1000003


import math

class Solution:

	def rank(self, S):
		i = 0
		n = len(S)
		ans = 1
		while i < len(S) - 1:
			count = 0
			for j in range(i + 1, len(S)):
				if S[i] > S[j]:
					count += 1
				elif S[i] == S[j]:
					return 0
			ans += math.factorial(n - i - 1) * count
			i += 1
		return ans % 1000003


import math

class Solution:

	def rank(self, S):
		dic = {}
		a = sorted(S)
		j = 0
		for i in a:
			if i in dic:
				return 0
			else:
				dic[i] = j
				j += 1
		i = 0
		n = len(S)
		ans = 1
		st = ''
		while i < len(S) - 1:
			for j in st:
				if S[i] > j:
					dic[S[i]] -= 1
			ans += math.factorial(n - i - 1) * dic[S[i]]
			st += S[i]
			i += 1
		return ans % 1000003


class Solution:

	def fact(self, num):
		x = 1
		while num > 0:
			x *= num
			num -= 1
		return x

	def rank(self, S):
		count = [0] * 26
		for char in S:
			index = ord(char) - ord('a')
			count[index] += 1
			if count[index] > 1:
				return 0
		curr_rank = 0
		pos = len(S) - 1
		for char in S:
			index = ord(char) - ord('a')
			ge = 0
			for i in range(index):
				if count[i] == 1:
					ge += 1
			count[index] = 0
			curr_rank += ge * self.fact(pos)
			pos -= 1
		return (curr_rank + 1) % 1000003


class Solution:

	def rank(self, S):
		n = len(S)
		fact = self.fact(n)
		arr = [0] * (256 + 1)
		for i in S:
			arr[ord(i)] += 1
			if arr[ord(i)] > 1:
				return 0
		for i in range(1, 257):
			arr[i] += arr[i - 1]
		rank = 1
		for i in S:
			fact //= n
			rank += arr[ord(i) - 1] * fact
			n -= 1
			for i in range(ord(i), 257):
				arr[i] -= 1
		return rank % 1000003

	def fact(self, n):
		if n == 0:
			return 1
		res = 1
		for i in range(1, n + 1):
			res *= i
		return res


def factorial(n):
	fact = 1
	for i in range(1, n + 1):
		fact = fact * i
	return fact

class Solution:

	def rank(self, s):
		rank = 1
		for i in range(len(s) - 1):
			count = 0
			for j in range(i + 1, len(s)):
				if s[i] > s[j]:
					count += 1
				elif s[i] == s[j]:
					return 0
			rank += count * factorial(len(s) - 1 - i)
		return rank % 1000003


class Solution:

	def fact(self, n):
		f = 1
		while n >= 1:
			f = f * n
			n = n - 1
		return f

	def findSmallerInRight(self, st, low, high):
		countRight = 0
		i = low + 1
		while i <= high:
			if st[i] < st[low]:
				countRight = countRight + 1
			i = i + 1
		return countRight

	def rank(self, S):
		st = set()
		for i in S:
			if i in st:
				return 0
			else:
				st.add(i)
		mod = 1000003.0
		ln = len(S)
		mul = self.fact(ln)
		rank = 1
		i = 0
		while i < ln:
			mul = mul // (ln - i)
			countRight = self.findSmallerInRight(S, i, ln - 1)
			rank = rank + countRight * mul
			i = i + 1
		return int(rank % mod)


class Solution:

	def rank(self, s):
		mod = 1000003
		n = len(s)
		if n == 1:
			return 1
		fact = [0] * n
		fact[0] = 1
		fact[1] = 1
		result = 0
		s_sorted = sorted(s)
		for i in range(2, n):
			fact[i] = fact[i - 1] * i % mod
		charmap = {}
		for i in range(n):
			char = s[i]
			if char in charmap:
				return 0
			elif char not in charmap:
				charmap[char] = 1
		for i in range(n):
			small_count = 0
			for j in range(n):
				if s_sorted[j] == s[i]:
					s_sorted[j] = '#'
					break
				if s_sorted[j] != '#':
					small_count += 1
			result = (result + small_count * fact[n - i - 1] % mod) % mod
		return (result + 1) % mod


class Solution:

	def rank(self, S):
		mod = 1000003

		def fact(n):
			if n <= 1:
				return 1
			return n * fact(n - 1)
		m = 256
		res = 1
		n = len(S)
		arr = [0] * (256 + 1)
		mul = fact(n)
		for i in range(n):
			arr[ord(S[i])] += 1
			if arr[ord(S[i])] > 1:
				return 0
		for i in range(1, m):
			arr[i] += arr[i - 1]
		for i in range(n):
			mul = mul // (n - i)
			res += arr[ord(S[i]) - 1] * mul
			for j in range(ord(S[i]), m):
				arr[j] -= 1
		return res % mod


class Solution:

	def fact(self, n):
		return 1 if n <= 1 else n * self.fact(n - 1)

	def populate_and_increase_count(self, s, count):
		for i in range(len(s)):
			count[ord(s[i])] += 1
		for i in range(1, 256):
			count[i] += count[i - 1]

	def updatecount(self, ch, count):
		for i in range(ord(ch), 256):
			count[i] -= 1

	def rank(self, S):
		if len(set(S)) != len(S):
			return 0
		maxchar = 256
		count = [0] * (maxchar + 1)
		len1 = len(S)
		mul = self.fact(len1)
		rank = 1
		self.populate_and_increase_count(S, count)
		for i in range(len1):
			mul = mul // (len1 - i)
			rank += count[ord(S[i]) - 1] * mul
			self.updatecount(S[i], count)
		return rank % 1000003


class Solution:

	def fact(self, n):
		if n <= 1:
			return 1
		if n == 2:
			return 2
		return n * self.fact(n - 1)

	def rank(self, S):
		if len(S) != len(set(S)):
			return 0
		st = sorted(S)
		if ''.join(st) == S:
			return 1
		count = 1
		for i in range(len(S)):
			for j in range(len(st)):
				if S[i] != st[j]:
					count += self.fact(len(S) - i - 1)
				else:
					st.pop(j)
					break
		return count % 1000003


from collections import Counter

class Solution:

	def nos(self, S, i):
		count = 0
		for x in range(i + 1, len(S)):
			if S[x] < S[i]:
				count += 1
		return count

	def fact(self, n):
		if n <= 1:
			return 1
		else:
			return n * self.fact(n - 1)

	def rank(self, S):
		for val in Counter(S).values():
			if val > 1:
				return 0
		n = len(S)
		i = 0
		rank = 1
		while i < n:
			ns = self.nos(S, i)
			perm = self.fact(n - i - 1)
			rank += ns * perm
			i += 1
		return rank % 1000003


import math

class Solution:

	def rank(self, s):
		if len(set(s)) is not len(s):
			return 0
		(rank, N) = (0, len(s))
		t = [0] * 26
		for c in s:
			t[ord(c) - ord('a')] += 1
		for i in range(N):
			ci = ord(s[i]) - ord('a')
			rank += math.factorial(N - 1 - i) * sum(t[:ci])
			t[ci] = 0
		return (rank + 1) % 1000003


import math

class Solution:

	def factorial(self, fact, n):
		(fact[0], fact[1]) = (1, 1)
		for i in range(2, n):
			fact[i] = fact[i - 1] * i % 1000003

	def rank(self, S):
		if len(list(set(S))) != len(S):
			return 0
		mod = 1000003
		(ans, ind, n, fact) = (1, 0, len(S), [0] * (len(S) + 1))
		self.factorial(fact, n)
		for i in range(n):
			less_than = 0
			for j in range(i + 1, n):
				if ord(S[i]) > ord(S[j]):
					less_than += 1
			f = fact[n - i - 1] % mod
			p = f * less_than % mod
			ans = (ans + p) % mod
		return ans


class Solution:

	def rank(self, S):

		def fact(n):
			f = 1
			while n >= 1:
				f = f * n
				n = n - 1
			return f

		def findSmallerInRight(st, low, high):
			countRight = 0
			i = low + 1
			while i <= high:
				if st[i] < st[low]:
					countRight = countRight + 1
				i = i + 1
			return countRight

		def findRank(st):
			ln = len(st)
			mul = fact(ln)
			rank = 1
			temp = {}
			for i in st:
				if temp.get(i):
					return 0
				else:
					temp[i] = 1
			i = 0
			while i < ln:
				mul = mul // (ln - i)
				countRight = findSmallerInRight(st, i, ln - 1)
				rank = rank + countRight * mul
				i = i + 1
			return rank
		return findRank(S) % 1000003


class Solution:

	def fact(self, n):
		a = 1
		while n > 0:
			a *= n
			n = n - 1
		return a

	def fun(self, S, i, j):
		count = 0
		for k in range(i + 1, j + 1):
			if S[k] < S[i]:
				count += 1
			elif S[k] == S[i]:
				return -1
		return count

	def rank(self, S):
		ln = len(S)
		k = self.fact(ln)
		i = 0
		ans = 1
		while i <= ln - 1:
			k = k / (ln - i)
			count = self.fun(S, i, ln - 1)
			if count < 0:
				return 0
			ans += count * k
			i += 1
		ans = ans % 1000003
		return int(ans)


class Solution:

	def rank(self, S):
		n = len(S)
		fact = 1
		for i in range(2, n + 1):
			fact *= i
		char = [0] * 27
		for i in S:
			if char[ord(i) - 97 + 1] != 0:
				return 0
			char[ord(i) - 97 + 1] += 1
		for i in range(1, 27):
			char[i] += char[i - 1]
		res = 0
		for i in range(n - 1):
			fact = fact // (n - i)
			res += char[ord(S[i]) - 97] * fact
			for j in range(ord(S[i]) - 97 + 1, 27):
				char[j] -= 1
		return (res + 1) % 1000003


class Solution:

	def rank(self, S):
		result = 1
		for i in range(len(S)):
			current_character = S[i]
			for j in range(i + 1, len(S)):
				if S[j] < current_character:
					result += factorial(len(S) - i - 1)
				if S[j] == current_character:
					return 0
		return result % 1000003

def factorial(n):
	if n == 1:
		return 1
	else:
		return n * factorial(n - 1)


class Solution:

	def rank(self, s):
		res = 1
		n = len(s)
		fact = 1
		char = [0] * 256
		for i in range(1, n + 1, 1):
			fact *= i
		for i in range(n):
			char[ord(s[i])] += 1
		for i in range(1, 256):
			if char[i] > 1:
				return 0
			char[i] += char[i - 1]
		for i in range(n - 1):
			fact = fact // (n - i)
			res = (res + char[ord(s[i]) - 1] * fact) % 1000003
			for j in range(ord(s[i]), 256, 1):
				char[j] -= 1
		return res % 1000003


class Solution:

	def rank(self, S):
		if len(S) > len(set(S)):
			return 0
		a = list(S)
		a.sort()
		c = 0
		n = len(S)
		for i in S:
			c = (c + self.fact(n - 1) * a.index(i)) % 1000003
			a.remove(i)
			n -= 1
		return c + 1

	def fact(self, n):
		f = 1
		while n > 1:
			f = f * n
			n -= 1
		return f


class Solution:

	def fact(self, n):
		if n == 0 or n == 1:
			return 1
		else:
			return n * self.fact(n - 1)

	def rank(self, s):
		l = sorted(s)
		n = len(s)
		if len(set(l)) < n:
			return 0
		ans = 0
		for i in s:
			ind = l.index(i)
			ans = (ans + self.fact(n - 1) * ind) % 1000003
			l.remove(i)
			n = n - 1
		return ans + 1


class Solution:

	def rank(self, S):
		s = set(S)
		if len(s) < len(S):
			return 0
		n = len(S)
		fact = list()
		fact.extend([1, 1])
		for i in range(2, 26):
			fact.append(i * fact[i - 1])
		arr = [0] * 256
		output = 0
		for i in range(n):
			arr[ord(S[i])] += 1
		for i in range(n):
			count = 0
			for j in range(256):
				if j == ord(S[i]):
					break
				if arr[j] == 1:
					count += 1
			arr[ord(S[i])] = 0
			output += count * fact[n - i - 1]
		return (output + 1) % 1000003


from collections import Counter

class Solution:

	def rank(self, S):
		cnts = Counter(S)
		if any([k for k in cnts if cnts[k] > 1]):
			return 0
		chars = sorted(cnts)
		rank = 1
		n = len(S)
		self.dp = dict()
		for (i, c) in enumerate(S):
			idx = chars.index(c)
			rank = (rank + idx * self.fact(n - 1 - i)) % 1000003
			chars.remove(c)
		return rank

	def fact(self, n):
		if n in self.dp:
			return self.dp[n]
		if n <= 1:
			return 1
		self.dp[n] = n * self.fact(n - 1)
		return self.dp[n] % 1000003