Given a string consisting of lower case English alphabets, the task is to find the number of distinct subsequences of the string
Note: Answer can be very large, so, ouput will be answer modulo 10^{9}+7
Example 1:
Input: s = "gfg"
Output: 7
Explanation: The seven distinct
subsequences are "", "g", "f", "gf", "fg",
"gg" and "gfg" 
Example 2:
Input: s = "ggg"
Output: 4
Explanation: The four distinct
subsequences are "", "g", "gg", "ggg"
Your task:
You do not need to read any input or print anything. The task is to complete the function distinctSubsequences(), which takes a string as input and returns an integer. 
Expected Time Complexity: O(|str|)
Expected Auxiliary Space: O(|str|)
Constraints:
1 ≤ |s| ≤ 10^{5}
s contains lower case English alphabets

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

	def distinctSubsequences(self, S):

		# code here

Solutions:
class Solution:

	def distinctSubsequences(self, s):
		n = len(s)
		dp = [0] * (n + 1)
		dp[0] = 1
		d = {}
		for i in range(1, n + 1):
			char = s[i - 1]
			dp[i] = dp[i - 1] * 2
			if char in d:
				idx = d[char]
				dp[i] -= dp[idx - 1]
			d[char] = i
		return dp[n] % 1000000007


class Solution:

	def distinctSubsequences(self, S):
		l = [1]
		st = ''
		for i in S:
			if i in st:
				p = len(st) - st[::-1].index(i) - 1
				l.append((l[-1] * 2 - l[p]) % (10 ** 9 + 7))
			else:
				l.append(l[-1] * 2 % (10 ** 9 + 7))
			st += i
		return l[len(l) - 1]


class Solution:

	def distinctSubsequences(self, S):
		s1 = S
		l = [0] * len(s1)
		l[0] = 2
		(h, h1) = ({}, {})
		for i in range(len(s1)):
			h[i] = h1.get(s1[i], -1)
			h1[s1[i]] = i
		for i in range(1, len(s1)):
			if h[i] == -1:
				l[i] = l[i - 1] * 2 % 1000000007
			elif h[i] == 0:
				l[i] = (l[i - 1] * 2 - 1) % 1000000007
			else:
				l[i] = l[i - 1] * 2 % 1000000007 - l[h[i] - 1] % 1000000007
		return l[-1] % 1000000007


class CntDistinctSubSeq_dyanmic_prog(object):

	def __init__(self):
		pass

	def cnt_dist_sseq(self, txt1: str) -> int:
		nsseq = self.cnt_through_dynamic(txt1)
		return nsseq

	def cnt_through_dynamic(self, txt1: str):
		lst = [0] * len(txt1)
		lst[0] = 2
		dt = {txt1[0]: 0}
		dt.update({'.': 1})
		for i in range(1, len(txt1)):
			lst[i] = 2 * lst[i - 1]
			if dt.get(txt1[i], -1) != -1:
				if dt.get(txt1[i], -1) != 0:
					lst[i] = lst[i] - lst[dt.get(txt1[i]) - 1]
				else:
					lst[i] = lst[i] - 1
			dt[txt1[i]] = i
		return lst[len(txt1) - 1] % (pow(10, 9) + 7)

class Solution:

	def distinctSubsequences(self, S):
		csseq = CntDistinctSubSeq_dyanmic_prog()
		return csseq.cnt_dist_sseq(S)


class Solution:

	def distinctSubsequences(self, S):
		m = {}
		dp = [1]
		for i in range(len(S)):
			if S[i] in m:
				dp.append(dp[i] * 2 - dp[m[S[i]] - 1])
			else:
				dp.append(dp[i] * 2)
			m[S[i]] = i + 1
		return dp[len(S)] % 1000000007


class Solution:

	def distinctSubsequences(self, S):
		last = [-1] * 26
		mod = 10 ** 9 + 7
		n = len(S)
		dp = [-2 for i in range(n + 1)]
		dp[0] = 1
		for i in range(1, n + 1):
			dp[i] = 2 * dp[i - 1]
			dp[i] %= mod
			if last[ord(S[i - 1]) - 97] != -1:
				dp[i] = dp[i] - dp[last[ord(S[i - 1]) - 97]]
				dp[i] %= mod
			last[ord(S[i - 1]) - 97] = i - 1
		return dp[n]


class Solution:

	def distinctSubsequences(self, s):
		n = len(s)
		dp = [0] * (n + 1)
		dp[0] = 1
		d = {}
		for i in range(1, n + 1):
			char = s[i - 1]
			dp[i] = dp[i - 1] * 2
			if char in d:
				idx = d[char]
				dp[i] -= dp[idx - 1]
			d[char] = i
		return dp[n] % (10 ** 9 + 7)


mod = 10 ** 9 + 7

class Solution:

	def distinctSubsequences(self, S):
		n = len(S)
		dp = [0] * (n + 1)
		dp[0] = 1
		last = {}
		for i in range(n):
			if S[i] not in last:
				dp[i + 1] = 2 * dp[i] % mod
			else:
				dp[i + 1] = (2 * dp[i] - dp[last[S[i]]]) % mod
			last[S[i]] = i
		return dp[n]


class Solution:

	def distinctSubsequences(self, S):
		last = [-1] * 256
		dp = [0] * (len(S) + 1)
		dp[0] = 1
		for i in range(1, len(S) + 1):
			dp[i] = dp[i - 1] * 2
			if last[ord(S[i - 1])] != -1:
				dp[i] -= dp[last[ord(S[i - 1])]]
			last[ord(S[i - 1])] = i - 1
		return dp[len(S)] % int(1000000000.0 + 7)


class Solution:

	def distinctSubsequences(self, s):
		last = [-1] * 123
		n = len(s)
		mod = 10 ** 9 + 7
		dp = [-2] * (n + 1)
		dp[0] = 1
		for i in range(1, n + 1):
			dp[i] = 2 * dp[i - 1] % mod
			if last[ord(s[i - 1])] != -1:
				dp[i] = (dp[i] - dp[last[ord(s[i - 1])]]) % mod
			last[ord(s[i - 1])] = i - 1
		return dp[n]


class Solution:

	def distinctSubsequences(self, S):
		M = 10 ** 9 + 7
		dp = [-1 for i in range(len(S) + 1)]
		dp[0] = 1
		map = {}
		for i in range(1, len(dp)):
			dp[i] = 2 * dp[i - 1]
			ch = S[i - 1]
			if ch in map.keys():
				j = map[ch]
				dp[i] = dp[i] - dp[j - 1]
			map[ch] = i
		return dp[len(S)] % M


class Solution:

	def distinctSubsequences(self, S):
		a = [0] * 27
		n = len(S)
		a[-1] = 1
		for r in range(n):
			a[ord(S[r]) - ord('a')] = sum(a)
		ans = 0
		m = 10 ** 9 + 7
		for i in a:
			ans += i
			ans %= m
		return ans


class Solution:

	def distinctSubsequences(self, S):
		dp = [1] * (len(S) + 1)
		hash = {}
		for i in range(1, len(dp)):
			dp[i] = 2 * dp[i - 1]
			if S[i - 1] in hash:
				x = hash[S[i - 1]]
				dp[i] = dp[i] - dp[x]
			hash[S[i - 1]] = i - 1
		return dp[len(S)] % (10 ** 9 + 7)


class Solution:

	def distinctSubsequences(self, S):
		dp = [0] * (len(S) + 1)
		dp[0] = 1
		dic = {}
		for i in range(1, len(dp)):
			dp[i] = dp[i - 1] * 2
			if S[i - 1] in dic:
				j = dic[S[i - 1]]
				dp[i] = dp[i] - dp[j - 1]
			dic[S[i - 1]] = i
		return dp[len(S)] % 1000000007


class Solution:

	def distinctSubsequences(self, S):
		n = len(S)
		dp = [0] * (n + 1)
		dp[0] = 1
		d = {}
		for i in range(1, n + 1):
			char = S[i - 1]
			dp[i] = dp[i - 1] * 2
			if char in d:
				index = d[char]
				dp[i] = dp[i] - dp[index - 1]
			d[char] = i
		return dp[n] % 1000000007


class Solution:

	def distinctSubsequences(self, s):
		dp = [0] * (len(s) + 1)
		dp[0] = 1
		res = {}
		for i in range(1, len(s) + 1):
			dp[i] = 2 * dp[i - 1]
			char = s[i - 1]
			if char in res:
				indx = res[char]
				dp[i] = dp[i] - dp[indx - 1]
			res[char] = i
		return dp[len(s)] % 1000000007


class Solution:

	def distinctSubsequences(self, s):
		dp = [0 for times in range(len(s) + 1)]
		dp[0] = 1
		lo = {}
		for idx in range(1, len(s) + 1):
			ch = s[idx - 1]
			dp[idx] = 2 * dp[idx - 1]
			if ch in lo:
				dp[idx] = dp[idx] - dp[lo[ch] - 1]
			lo[ch] = idx
		return dp[len(s)] % 1000000007


class Solution:

	def distinctSubsequences(self, S):
		dp = [1]
		last = {}
		for (i, x) in enumerate(s):
			dp.append(dp[-1] * 2)
			if x in last:
				dp[-1] -= dp[last[x]]
			last[x] = i
		return dp[-1] % (10 ** 9 + 7)


class Solution:

	def distinctSubsequences(self, S):
		dp = [0] * (len(S) + 1)
		words = {}
		dp[0] = 1
		for i in range(1, len(S) + 1):
			dp[i] = 2 * dp[i - 1]
			char = S[i - 1]
			if char in words:
				indx = words[char]
				dp[i] = dp[i] - dp[indx - 1]
			words[char] = i
		return dp[len(S)] % 1000000007


class Solution:

	def distinctSubsequences(self, S):
		end = [0] * 26
		for c in S:
			end[ord(c) - ord('a')] = sum(end) + 1
		return (sum(end) + 1) % (10 ** 9 + 7)


class Solution:

	def distinctSubsequences(self, S):
		mod = 10 ** 9 + 7
		n = len(S)
		hm = {}
		dp = [0] * (n + 1)
		dp[0] = 1
		for i in range(1, n + 1):
			if S[i - 1] in hm:
				lastocc = hm[S[i - 1]]
				cntbeforelastocc = dp[lastocc - 1]
				dp[i] = (2 * dp[i - 1] - cntbeforelastocc) % mod
			else:
				dp[i] = 2 * dp[i - 1] % mod
			hm[S[i - 1]] = i
		return dp[n]


class Solution:

	def distinctSubsequences(self, S):
		n = len(S)
		dp = [0] * (n + 1)
		dp[0] = 1
		hashmap = {}
		for i in range(1, n + 1):
			char = s[i - 1]
			dp[i] = 2 * dp[i - 1]
			if char in hashmap:
				lstOccur = hashmap[char]
				dp[i] -= dp[lstOccur - 1]
			hashmap[char] = i
		return dp[n] % (10 ** 9 + 7)


class Solution:

	def distinctSubsequences(self, s):
		n = len(s)
		dp = [0] * (n + 1)
		dp[0] = 1
		l = [-1] * 257
		for i in range(1, n + 1):
			dp[i] = 2 * dp[i - 1]
			if l[ord(s[i - 1])] != -1:
				dp[i] -= dp[l[ord(s[i - 1])]]
			l[ord(s[i - 1])] = i - 1
		return dp[n] % 1000000007


class Solution:

	def distinctSubsequences(self, S):
		dp = [0 for i in range(len(S) + 1)]
		dp[0] = 1
		store = {}
		for i in range(1, len(dp)):
			dp[i] = 2 * dp[i - 1]
			if S[i - 1] in store:
				j = store[S[i - 1]]
				dp[i] -= dp[j - 1]
			store[S[i - 1]] = i
		return dp[-1] % (pow(10, 9) + 7)


MOD = 10 ** 9 + 7

class Solution:

	def distinctSubsequences(self, S):
		n = len(S)
		dp = [0] * (n + 1)
		dp[0] = 1
		last_occur = {}
		for i in range(1, n + 1):
			dp[i] = 2 * dp[i - 1] % MOD
			ch = S[i - 1]
			if ch in last_occur:
				j = last_occur[ch]
				dp[i] = dp[i] - dp[j]
				dp[i] = dp[i] % MOD
			last_occur[ch] = i - 1
		return dp[n]


class Solution:

	def distinctSubsequences(self, S):
		n = len(S)
		dp = [0 for i in range(n + 1)]
		dp[0] = 1
		map = {}
		for i in range(1, n + 1):
			dp[i] = 2 * dp[i - 1]
			if S[i - 1] in map:
				j = map[S[i - 1]]
				dp[i] = dp[i] - dp[j - 1]
			map[S[i - 1]] = i
		return dp[n] % (10 ** 9 + 7)


class Solution:

	def distinctSubsequences(self, S):
		dp = [1]
		Map = {}
		n = len(S)
		mod = 1000000007
		for val in range(n):
			dp.append(2 * dp[val] % mod)
			if S[val] in Map:
				ind = Map[S[val]]
				dp[val + 1] = (dp[val + 1] % mod - dp[ind - 1] % mod) % mod
			Map[S[val]] = val + 1
		return dp[len(dp) - 1]


class Solution:

	def distinctSubsequences(self, s):
		astha = 1000000000.0 + 7
		pizza = [0] * (len(s) + 1)
		pizza[0] = 1
		d = {}
		for i in range(1, len(s) + 1):
			burger = s[i - 1]
			pizza[i] = pizza[i - 1] * 2
			if burger in d:
				fruty = d[burger]
				pizza[i] -= pizza[fruty - 1]
			d[burger] = i
		return int(pizza[len(s)] % astha)


class Solution:

	def distinctSubsequences(self, s):
		n = len(s)
		MOD = 1000000000.0 + 7
		dp = [0 for _ in range(n + 1)]
		index = {}
		dp[0] = 1
		for i in range(1, n + 1):
			ch = s[i - 1]
			dp[i] = dp[i - 1] * 2 % MOD
			if ch in index:
				idx = index[ch]
				dp[i] = (dp[i] - dp[idx - 1] + MOD) % MOD
			index[ch] = i
		return int(dp[n])


MOD = int(1000000000.0 + 7)

def f(A, idx, chars, mp, dp):
	if idx == len(A):
		mp[chars] = 1
		return 0
	mp[chars] = 1
	f(A, idx + 1, chars + A[idx], mp, dp)
	f(A, idx + 1, chars, mp, dp)
	dp[idx] = len(mp) % MOD
	return dp[idx]

class Solution:

	def distinctSubsequences(self, S):
		N = len(S)
		dp = [-1] * (N + 1)
		mp = {}
		ans = 0
		dp[0] = 1
		for i in range(1, N + 1):
			dp[i] = 2 * dp[i - 1]
			o = ord(S[i - 1]) - ord('a')
			if o in mp:
				dp[i] -= dp[mp[o]]
			mp[o] = i - 1
			dp[i] %= MOD
		return dp[-1]


class Solution:

	def distinctSubsequences(self, S):
		d = {}
		ans = 1
		arr = [1 for i in range(len(S))]
		for i in range(len(S)):
			if S[i] not in d:
				arr[i] = 2 * arr[i - 1]
			else:
				arr[i] = 2 * arr[i - 1] - arr[d[S[i]] - 1]
			d[S[i]] = i
		return arr[-1] % 1000000007


class Solution:

	def distinctSubsequences(self, S):
		map = {}
		for x in s:
			map[x] = -1
		all = 0
		level = 0
		for x in range(len(s)):
			c = s[x]
			if x == 0:
				all = 1
				map[c] = 1
				level = 1
				continue
			level = all + 1
			if map[c] < 0:
				all += level
			else:
				all += level - map[c]
			map[c] = level
		return (all + 1) % 1000000007


class Solution:

	def distinctSubsequences(self, S):
		n = len(S)
		dp = [0] * (n + 1)
		dp[0] = 1
		dic = {}
		for i in range(1, n + 1):
			dp[i] = 2 * dp[i - 1]
			if S[i - 1] in dic:
				k = dic[S[i - 1]]
				dp[i] -= dp[k - 1]
			dic[S[i - 1]] = i
		return dp[-1] % (10 ** 9 + 7)


class Solution:

	def distinctSubsequences(self, S):
		dp = [0] * (len(S) + 1)
		dp[0] = 1
		last = [0] * 26
		for i in range(1, len(S) + 1):
			idx = ord(S[i - 1]) - ord('a')
			j = last[idx]
			dup = dp[j - 1] if j > 0 else 0
			dp[i] = dp[i - 1] * 2 - dup
			last[idx] = i
		mod = 10 ** 9 + 7
		return dp[-1] % mod


class Solution:

	def distinctSubsequences(self, S):
		(dp, m) = ([0] * len(s), 10 ** 9 + 7)
		for (i, char) in enumerate(S):
			ind = S.rfind(char, 0, i)
			dp[i] = 1 + sum(dp[:i]) % m if ind == -1 else sum(dp[ind:i]) % m
		return sum(dp) % m + 1


import numpy as np

class Solution:

	def distinctSubsequences(self, S):
		dp = [1]
		last = {}
		for (i, x) in enumerate(S):
			dp.append(dp[-1] * 2)
			if x in last:
				dp[-1] -= dp[last[x]]
			last[x] = i
		return (dp[-1] - 1 + 1) % (10 ** 9 + 7)


from collections import defaultdict

class Solution:

	def distinctSubsequences(self, S):
		mod = 1000000007
		n = len(S)
		dp = [1 for i in range(len(S) + 1)]
		dm = defaultdict(lambda : 0)
		for i in range(1, n + 1, 1):
			dp[i] = dp[i - 1] % mod * (2 % mod) % mod
			if S[i - 1] in dm:
				val = dm[S[i - 1]]
				dp[i] = (dp[i] % mod - dp[val - 1] % mod) % mod
			dm[S[i - 1]] = i
		return dp[n]


from collections import defaultdict

class Solution:

	def distinctSubsequences(self, s):
		ans = 1
		mo = 10 ** 9 + 7
		dp = defaultdict(int)
		for i in s:
			(ans, dp[i]) = ((2 * ans - dp[i]) % mo, ans)
		return ans % mo


class Solution:

	def distinctSubsequences(self, S):
		n = len(S)
		dp = [0] * (n + 1)
		d = dict()
		dp[0] = 1
		for i in range(1, n + 1):
			dp[i] = 2 * dp[i - 1]
			ch = S[i - 1]
			if ch in d:
				idx = d.get(ch)
				dp[i] = dp[i] - dp[idx - 1]
			d[ch] = i
		return int(dp[n] % (1000000000.0 + 7))


class Solution:

	def distinctSubsequences(self, S):
		length = len(S)
		last_index = {}
		distinct_count = {0: 1}
		for i in range(1, length + 1):
			distinct_count[i] = 2 * distinct_count[i - 1]
			if S[i - 1] in last_index:
				distinct_count[i] -= distinct_count[last_index[S[i - 1]]]
			last_index[S[i - 1]] = i - 1
		return distinct_count[length] % (10 ** 9 + 7)


class Solution:

	def distinctSubsequences(self, s):
		dp = [0] * (len(s) + 1)
		dp[0] = 1
		res = {}
		for i in range(1, len(s) + 1):
			dp[i] = 2 * dp[i - 1]
			char = s[i - 1]
			if char in res:
				indx = res[char]
				dp[i] = dp[i] - dp[indx - 1]
			res[char] = i
		return dp[len(s)] % 1000000007
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.distinctSubsequences(s)
		print(answer)


class Solution:

	def distinctSubsequences(self, S):
		MAX = 128 * 2
		visited = [-1] * (MAX + 1)
		n = len(S)
		dp = [-2 for i in range(n + 1)]
		dp[0] = 1
		for i in range(1, n + 1):
			dp[i] = dp[i - 1] * 2
			if visited[ord(S[i - 1])] != -1:
				dp[i] = dp[i] - dp[visited[ord(S[i - 1])]]
			visited[ord(S[i - 1])] = i - 1
		result = dp[n]
		result = result % (10 ** 9 + 7)
		return result
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.distinctSubsequences(s)
		print(answer)


class Solution:

	def distinctSubsequences(self, S):
		dp = [0 for i in range(len(S) + 1)]
		dp2 = [-1 for i in range(257)]
		dp[0] = 1
		for i in range(1, len(S) + 1):
			if dp2[ord(S[i - 1])] == -1:
				dp[i] = 2 * dp[i - 1]
			else:
				dp[i] = 2 * dp[i - 1] - dp[dp2[ord(S[i - 1])]]
			dp2[ord(S[i - 1])] = i - 1
		return dp[len(S)] % (10 ** 9 + 7)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.distinctSubsequences(s)
		print(answer)


class Solution:

	def distinctSubsequences(self, S):
		n = len(S)
		dp = [0] * (n + 1)
		dp[0] = 1
		m = {}
		for i in range(1, n + 1):
			ch = S[i - 1]
			dp[i] = 2 * dp[i - 1]
			if ch in m:
				j = m[ch]
				dp[i] = dp[i] - dp[j - 1]
			m[ch] = i
		return dp[n] % 1000000007
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.distinctSubsequences(s)
		print(answer)


class Solution:

	def distinctSubsequences(self, s):
		d = {}
		n = len(s)
		dp = [0] * (n + 1)
		dp[0] = 1
		for i in range(1, n + 1):
			dp[i] = 2 * dp[i - 1]
			if s[i - 1] in d:
				dp[i] -= dp[d[s[i - 1]] - 1]
			dp[i] = dp[i] % (10 ** 9 + 7)
			d[s[i - 1]] = i
		return dp[-1] % (10 ** 9 + 7)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.distinctSubsequences(s)
		print(answer)


class Solution:

	def distinctSubsequences(self, S):
		dt = {}
		count = 1
		for i in S:
			if i not in dt:
				dt[i] = count
				count = 2 * count
			else:
				save = dt[i]
				dt[i] = count
				count = 2 * count - save
		return count % 1000000007
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.distinctSubsequences(s)
		print(answer)


class Solution:

	def distinctSubsequences(self, S):
		n = len(S)
		dp = [0] * (n + 1)
		dp[0] = 1
		dict = {}
		m = 10 ** 9 + 7
		for i in range(1, n + 1):
			dp[i] = 2 * dp[i - 1]
			ch = S[i - 1]
			if dict.get(ch) is not None:
				j = dict.get(ch)
				dp[i] = dp[i] - dp[j - 1]
			dict[ch] = i
		return dp[n] % m


class Solution:

	def distinctSubsequences(self, s):
		n = len(s)
		char = {}
		dp = [0 for i in range(n + 1)]
		dp[0] = 1
		for i in range(1, n + 1):
			if s[i - 1] not in char:
				char[s[i - 1]] = i - 1
				dp[i] = 2 * dp[i - 1]
			else:
				dp[i] = 2 * dp[i - 1] - dp[char[s[i - 1]]]
				char[s[i - 1]] = i - 1
		return dp[-1] % 1000000007


class Solution:

	def distinctSubsequences(self, S):
		n = len(S)
		count = [0 for i in range(n + 1)]
		count[0] = 1
		index = {}
		for i in range(n):
			if S[i] not in index.keys():
				count[i + 1] = count[i] * 2 % (10 ** 9 + 7)
			else:
				count[i + 1] = (count[i] * 2 - index[S[i]]) % (10 ** 9 + 7)
			index[S[i]] = count[i]
		return count[n]


class Solution:

	def distinctSubsequences(self, S):
		l = [0 for i in range(len(S))]
		s = 0
		d = {}
		v = {}
		for i in range(len(S) - 1, -1, -1):
			if v.get(S[i], 0) == 0:
				d[S[i]] = s
				l[i] = s + 1
				s += l[i]
			else:
				l[i] = s - d[S[i]]
				d[S[i]] = s
				s += l[i]
			v[S[i]] = 1
		return (sum(l) + 1) % (10 ** 9 + 7)


class Solution:

	def distinctSubsequences(self, S):
		l = [0 for i in range(len(s))]
		l[-1] = 1
		for i in range(len(s) - 2, -1, -1):
			curr = 0
			for j in range(i + 1, len(s)):
				if s[j] != s[i]:
					curr += l[j]
				else:
					curr += l[j]
					break
			else:
				curr += 1
			l[i] = curr
		return (sum(l) + 1) % (10 ** 9 + 7)


mod = 10 ** 9 + 7

class Solution:

	def distinctSubsequences(self, S):
		n = len(s)
		dp = [0] * (n + 1)
		dp[0] = 1
		d = {}
		for i in range(1, n + 1):
			dp[i] = 2 * dp[i - 1] % mod
			if S[i - 1] in d:
				j = d[S[i - 1]]
				dp[i] = (dp[i] - dp[j - 1]) % mod
			d[S[i - 1]] = i
		return dp[n] % mod


class Solution:

	def distinctSubsequences(self, s):
		mod = 1000000007
		l = [0 for _ in range(26)]
		n = len(s)
		dp = [0 for _ in range(n + 1)]
		dp[0] = 1
		for i in range(1, n + 1):
			x = s[i - 1]
			t = dp[i - 1]
			dp[i] = (2 * dp[i - 1] - l[ord(x) - 97]) % mod
			l[ord(x) - 97] = t
		return dp[-1] % mod


class Solution:

	def distinctSubsequences(self, s):
		mod = 1000000007
		l = [0 for _ in range(26)]
		for x in s:
			c = 1
			c += sum(l)
			c %= mod
			l[ord(x) - 97] = c
		return (sum(l) + 1) % mod


class Solution:

	def distinctSubsequences(self, ss):
		MAX_CHAR = 256
		last = [-1 for i in range(MAX_CHAR + 1)]
		n = len(ss)
		dp = [-2 for i in range(n + 1)]
		dp[0] = 1
		for i in range(1, n + 1):
			dp[i] = 2 * dp[i - 1]
			if last[ord(ss[i - 1])] != -1:
				dp[i] = dp[i] - dp[last[ord(ss[i - 1])]]
			last[ord(ss[i - 1])] = i - 1
		return dp[n] % (10 ** 9 + 7)


class Solution:

	def distinctSubsequences(self, S):
		string = S
		dic = {}
		dp = [0] * (len(string) + 1)
		for i in range(len(string)):
			if string[i] in dic:
				dp[i + 1] = dp[i] * 2 - dp[dic[string[i]] - 1]
			else:
				dp[i + 1] = dp[i] * 2 + 1
			dic[string[i]] = i + 1
		return (dp[-1] + 1) % (10 ** 9 + 7)