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 ; One by constructs remaining rows of Pascal Triangle from top to bottom ; Fill entries of current row using previous row values ; nCj = ( n - 1 ) Cj + ( n - 1 ) C ( j - 1 ) ; ; 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 . return ( nCrModpLucas ( parseInt ( n / p ) , parseInt ( r / p ) , p ) * Last digits of n and r nCrModpDP ( ni , ri , p ) ) % p ; Remaining digits ; Driver program
function nCrModpDP ( n , r , p ) { C = Array ( r + 1 ) . fill ( 0 ) ; for ( var i = 1 ; i <= n ; i ++ ) { for ( var j = Math . 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 ; var ni = n % p , ri = r % p ; } var n = 1000 , r = 900 , p = 13 ; document . write ( " " + nCrModpLucas ( n , r , p ) ) ;