title: Finding number of subsets of an array that add up to a multiple of a specific number
body: <p><strong>I have an array A of length N of negative as well as positive integers. I need to count the number of subsets in this array which add up to a multiple of a number M (or 0 (mod M))</strong><br>
  For example:<br><br>
  Let A = {1,2,8,4,5}, M = 9,<br>
  Then, there are 4 such subsets:<br></p>
  
  <ul>
  <li>{}: Empty set, corresponding to the multiple 0,</li>
  <li>{1,8}: corresponding to the multiple 9,</li>
  <li>{4,5}: corresponding to the multiple 9</li>
  <li>{1,8,4,5}: corresponding to the multiple 18.</li>
  </ul>
  
  <p>I thought of generating all possible multiples and then applying dynamic programming subset sum, but the constraints won't allow me that.<br><br>
  <b>Constraints:</b><br>
  1 =&lt; N &lt;= 10^5,<br>
  1 =&lt; M &lt;= 100,<br>
  -10^9 =&lt; each entry of array &lt;=10^9<br></p>
  
  <p>What should be my approach for this sort of problem?</p>