Find the last digit of given series | Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; $x = $x % $p ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now $y = $y >> 1 ; y = y / 2 ; Returns modulo inverse of a with respect to m using extended Euclid Algorithm ; q is quotient ; m is remainder now , process same as Euclid 's algo  ; Make x1 positive ; Function to calculate the above expression ; Initialize the result ; Compute first part of expression ; Compute second part of expression i . e . , ( ( 4 ^ ( n + 1 ) - 1 ) / 3 ) mod 10 Since division of 3 in modulo can ' t ▁ ▁ ▁ be ▁ performed ▁ directly ▁ therefore ▁ we ▁ ▁ ▁ need ▁ to ▁ find ▁ it ' s modulo Inverse ; Driver code
< ? php function powermod ( $ x , $ y , $ p ) { while ( $ y > 0 ) { if ( ( $ y & 1 ) > 0 ) $ res = ( $ res * $ x ) % $ p ; $ x = ( $ x * $ x ) % $ p ; } return $ res ; } function modInverse ( $ a , $ m ) { $ m0 = $ m ; $ x0 = 0 ; $ x1 = 1 ; if ( $ m == 1 ) return 0 ; while ( $ a > 1 ) { $ q = ( int ) ( $ a / $ m ) ; $ t = $ m ; $ m = $ a % $ m ; $ a = $ t ; $ t = $ x0 ; $ x0 = $ x1 - $ q * $ x0 ; $ x1 = $ t ; } if ( $ x1 < 0 ) $ x1 += $ m0 ; return $ x1 ; } function evaluteExpression ( $ n ) { $ firstsum = 0 ; $ mod = 10 ; for ( $ i = 2 , $ j = 0 ; ( 1 << $ j ) <= $ n ; $ i *= $ i , ++ $ j ) $ firstsum = ( $ firstsum + $ i ) % $ mod ; $ secondsum = ( powermod ( 4 , $ n + 1 , $ mod ) - 1 ) * modInverse ( 3 , $ mod ) ; return ( $ firstsum * $ secondsum ) % $ mod ; } $ n = 3 ; echo evaluteExpression ( $ n ) . " STRNEWLINE " ; $ n = 10 ; echo evaluteExpression ( $ n ) ; ? >