A Function to calculate the prefix hash
static void computePrefixHash ( String str , int n , int [ ] prefix , 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 ; }