Calculating binomial coefficient using DP
for ( int i = 0 ; i <= n ; i ++ ) { c [ i ] [ 0 ] = 1 ; for ( int j = 1 ; j <= i ; j ++ ) { c [ i ] [ j ] = ( c [ i - 1 ] [ j ] + c [ i - 1 ] [ j - 1 ] ) % mod ; } } powOf2 [ 0 ] = powOf2 [ 1 ] = 1 ;