You are provided an input string S and the string “GEEKS” . Find the number of ways in which the subsequence “GEEKS” can be formed from the string S.

Example 1:
Input : S = "GEEKS"
Output: 1
Explanation:
"GEEKS" occurs in S only once.
Example 2:
Input: S = "AGEEKKSB"
Output: 2
Explanation: Subsequenece "GEEKS" occurs in
S two times. First one is taking the first
'K' into consideration and second one is
taking second 'K'.

Your Task:
You don't need to read or print anything. Your task is to complete the function TotalWays() which takes string S as input paramater and returns total ways modulo 10^{9} + 7.

Expected Time Complexity : O(N * K) where N is length of string and K is constant.
Expected Space Complexity: O(N * K)

Constraints:
1 <= Length od string <= 10000

见题面

见题面