The hash of a 0-indexed string s of length k, given integers p and m, is computed using the following function:


	hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m.


Where val(s[i]) represents the index of s[i] in the alphabet from val('a') = 1 to val('z') = 26.

You are given a string s and the integers power, modulo, k, and hashValue. Return sub, the first substring of s of length k such that hash(sub, power, modulo) == hashValue.

The test cases will be generated such that an answer always exists.

A substring is a contiguous non-empty sequence of characters within a string.

&nbsp;
Example 1:

Input: s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0
Output: "ee"
Explanation: The hash of "ee" can be computed to be hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0. 
"ee" is the first substring of length 2 with hashValue 0. Hence, we return "ee".


Example 2:

Input: s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
Output: "fbx"
Explanation: The hash of "fbx" can be computed to be hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 312) mod 100 = 23132 mod 100 = 32. 
The hash of "bxz" can be computed to be hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32. 
"fbx" is the first substring of length 3 with hashValue 32. Hence, we return "fbx".
Note that "bxz" also has a hash of 32 but it appears later than "fbx".


&nbsp;
Constraints:


	1 &lt;= k &lt;= s.length &lt;= 2 * 104
	1 &lt;= power, modulo &lt;= 109
	0 &lt;= hashValue &lt; modulo
	s consists of lowercase English letters only.
	The test cases are generated such that an answer always exists.


class Solution:
    def subStrHash(self, s: str, power: int, mod: int, k: int, hashValue: int) -> str:
        val = lambda ch : ord(ch) - ord("a") + 1
        hash, res, power_k = 0, 0, pow(power, k, mod)
        for i in reversed(range(len(s))):
            hash = (hash * power + val(s[i])) % mod
            if i < len(s) - k:
                hash = (mod + hash - power_k * val(s[i + k]) % mod) % mod
            res = i if hash == hashValue else res
        return s[res:res + k]
class Solution {
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
		// calculate all the powers from power^0 till power^k
		// utilized binary exponentiation
		long[] powers = new long[k];
        for (int i = 0; i < k; i++) 
            powers[i] = binaryExponentiation(power, i, modulo);
        
		// pre compute the initial hash from behind.
		// I have explained at top you why traversing from behind is easy
        long currentHashValue = 0;
        int index = s.length() - 1;
        int powerIndex = k-1;
        while (index >= s.length() - k) {
			// (a+b) % modulo = ( (a % modulo) + (b % modulo) ) % modulo;
			// do it for k times from behind
            currentHashValue += ((s.charAt(index--) - 'a' + 1) % modulo * powers[powerIndex--] % modulo) % modulo;
        }
        currentHashValue %= modulo;
        
        int startIndex = 0;
        if (currentHashValue == hashValue) {
            startIndex = s.length() - k;
        }
        
		// I have pre computed already for k values from behind. so start from (length of S - k - 1)
		// Let's take an example of "leetcode" itself
		// "de" is pre computed
		// point is to add one character from behind and remove one from end (Sliding from back to first)
		// Modular Arithmetic for (a-b) % modulo = ( (a % modulo) - (b % modulo) + modulo) % modulo;
		// keep tracking of the start index if hash value matches. That's it.
        for (int i = s.length() - k - 1; i >= 0; i--) {
			// below line a --> currentHashValue 
			// below line b --> (s.charAt(i+k) - 'a' + 1 * powers[k-1])
            currentHashValue = ((currentHashValue % modulo) - (((s.charAt(i+k) - 'a' + 1) * powers[k-1]) % modulo) + modulo) % modulo;
			// we need to multiply a power once for all
			// MULTIPLICATION
            currentHashValue = currentHashValue * power;
			// Modular Arithmetic for (a+b) % modulo is below line
            currentHashValue = (currentHashValue % modulo + (s.charAt(i) - 'a' + 1) % modulo) % modulo;
            
            if (currentHashValue == hashValue) {
                startIndex = i;
            }
        }
        return s.substring(startIndex, startIndex+k);
    }
    
    private long binaryExponentiation(long a, long b, long mod) {
        a %= mod;
        long result = 1;
        while (b > 0) {
            if (b % 2 == 1)
                result = result * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return result;
    }
}
'''
class Solution {
public:
    string subStrHash(string s, int power, int modulo, int k, int hashValue) {
        int n=s.size();                         
        long long int sum=0;
        long long int p=1;
		// Intializing a window from end of size k 
        for(int i=0;i<k;i++){
                sum=(sum+((s[n-k+i]-'a'+1)*p));         
                if(i!=k-1)
                    p=(p*power)%modulo;
        }
		// storing the res when ever we get required answer
        int res=n-k;   // storing the res when ever we get required answer
		// slide window to right and removing ith index element and adding (i-k)th index element 
        for(int i=n-1;i>=k;i--)
		{                                          
		//removing last element from window
                sum-=(s[i]-'a'+1)*(p%modulo);               
				 // dividing by modulo to avoid integer overflow conditions
                sum=sum%modulo;                  
				 // muliplying the given string by power
                sum=sum*(power%modulo);            
				 // adding (i-k)th element in the window  
                sum+=s[i-k]-'a'+1;                 
				 // if sum < 0 then it created problem in modulus thats why making it positive
            while(sum%modulo<0){                              
                sum=sum+modulo;
            }
            if(sum%modulo==hashValue){
                res=i-k;                                           // storing the starting window index because we have to return the first string from starting 
            }
        }
        return s.substr(res,k);
    }
};
'''
let arrChar ="1abcdefghijklmnopqrstuvwxyz".split("");
var subStrHash = function(s, power, modulo, k, hashValue) {
  
    for(let i=0;i<s.length;i++){
        let subStr = s.substring(i,i+k);
        if(hash(subStr,power,modulo)==hashValue){
            return subStr;
        }
    }
};
let hash = function(str,power,m){
    let result=0;
    for(let i=0;i<str.length;i++){
        result += arrChar.indexOf(str[i])*Math.pow(power,i);
    }
    return result%m;
}
Find Substring With Given Hash Value