A Function to calculate the prefix hash
void computePrefixHash ( string str , int n , unsigned long long int prefix [ ] , unsigned long long int power [ ] ) { prefix [ 0 ] = 0 ; prefix [ 1 ] = str [ 0 ] ; for ( int i = 2 ; i <= n ; i ++ ) prefix [ i ] = ( prefix [ i - 1 ] % MOD + ( str [ i - 1 ] % MOD * power [ i - 1 ] % MOD ) % MOD ) % MOD ; return ; }