Compute nCr % p | Set 2 ( Lucas Theorem ) | Returns nCr % p . In this Lucas Theorem based program , this function is only called for n < p and r < p . ; The array C is going to store last row of pascal triangle at the end . And last entry of last row is nCr ; Top row of Pascal Triangle ; One by constructs remaining rows of Pascal Triangle from top to bottom ; Fill entries of current row using previous row values ; Lucas Theorem based function that returns nCr % p . This function works like decimal to binary conversion recursive function . First we compute last digits of n and r in base p , then recur for remaining digits ; Base case ; Compute last digits of n and r in base p ; Compute result for last digits computed above , and for remaining digits . Multiply the two results and compute the result of multiplication in modulo p . ; $r / $p , $p ) * Last digits of n and r nCrModpDP ( $ni , $ri , $p ) ) % $p ; Remaining digits ; Driver Code
< ? php function nCrModpDP ( $ n , $ r , $ p ) { $ C = array_fill ( 0 , $ n + 1 , false ) ; $ C [ 0 ] = 1 ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { for ( $ j = min ( $ i , $ r ) ; $ j > 0 ; $ j -- ) $ C [ $ j ] = ( $ C [ $ j ] + $ C [ $ j - 1 ] ) % $ p ; } return $ C [ $ r ] ; } function nCrModpLucas ( $ n , $ r , $ p ) { if ( $ r == 0 ) return 1 ; $ ni = $ n % $ p ; $ ri = $ r % $ p ; return ( nCrModpLucas ( $ n / $ p , } $ n = 1000 ; $ r = 900 ; $ p = 13 ; echo " Value ▁ of ▁ nCr ▁ % ▁ p ▁ is ▁ " , nCrModpLucas ( $ n , $ r , $ p ) ; ? >