Counting combinations modulo power of 2

It is pretty simple to calculate the number of ways to choose k items out of n: There are n ways to choose the first item, n-1 ways to choose the second item, and so on, until there are \(n-k+1\) ways to choose the kth item. By the rule of product there are \(n (n-1)···(n-k+1)\) ways …