title: Number of Positive Solutions to a1 x1+a2 x2+......+an xn=k (k<=10^18)
body: <p>The question is Number of solutions to a1 x1+a2 x2+....+an xn=k with constraints: 1)ai>0 and ai&lt;=15 2)n>0 and n&lt;=15 3)xi>=0 I was able to formulate a Dynamic programming solution but it is running too long for n>10^10. Please guide me to get a more efficient soution.
  The code</p>
  
  <pre><code>int dp[]=new int[16];
          dp[0]=1;
          BigInteger seen=new BigInteger("0");
          while(true)
          {
              for(int i=0;i&lt;arr[0];i++)
              {
                  if(dp[0]==0)
                      break;
                  dp[arr[i+1]]=(dp[arr[i+1]]+dp[0])%1000000007;
              }
              for(int i=1;i&lt;15;i++)
                  dp[i-1]=dp[i];
              seen=seen.add(new BigInteger("1"));
              if(seen.compareTo(n)==0)
              break;
          }
          System.out.println(dp[0]);
  </code></pre>
  
  <p>arr is the array containing coefficients and answer should be mod 1000000007 as the number of ways donot fit into an int.</p>