title: Count number of subsequences with given k modulo sum
body: <p>Given an array <code>a</code> of <code>n</code> integers, count how many subsequences (non-consecutive as well) have <code>sum % k = 0</code>:</p>
  
  <pre><code>1 &lt;= k &lt; 100
  1 &lt;= n &lt;= 10^6
  1 &lt;= a[i] &lt;= 1000
  </code></pre>
  
  <p>An <code>O(n^2)</code> solution is easily possible, however a faster way <code>O(n log n)</code> or <code>O(n)</code> is needed.</p>