Statement

  The following problem was given at a Romanian national contest in 2016, I've solved it quite a long time ago but only now have i got around to showing it to you. You are given a positive natural number S <= 10^5 and you are required to print the number of non-decreasing sequences with sum S or less modulo 666013. For example if S = 4 the answer is 11 (the sequences are {1}, {1, 1} ,{1, 1, 1}, {1, 1, 1, 1}, {1, 1, 2}, {1, 2}, {1, 3}, {2}, {2, 2}, {3}, {4}). You've also got 1 second and only 8MB of memory. The solution has 3 parts so if you want to try it yourself you may read one paragraph at a time for hints.  

The first DP to discover

  Your first idea to attack this problem might be a DP[x][s] counting the number of sequences starting with x or more and total sum s or less. The reccurence relation is DP[x][s] = DP[x+1][s] + DP[x][s-x]. DP[x+1][s] counts the number of sequences starting with strictly more than x and DP[x][s-x] counts how many start with exactly x, thus substracting x from the total sum. Your answer will be at DP[1][S] and you will be delighted to have found a quadratic solution so quickly but soon will start to worry that there is no optimization for this reccurence. You may notice however that when x is large, say larger than sqrt(S) there will be very few numbers possible in the sequences, at most sqrt(S), so you may start looking for a solution that uses how many numbers you put in a sequence rather than how large is the first number in it.

A different approach to explore

  After you decided to look for DPs with a set number of numbers in the sequence you quickly found DP2[n][s] counting the number of sequences with exactly n numbers and sum s or less. The reccurence for this one is DP2[n][s] = DP2[n][s-n] + DP2[n-1][s-1]. DP2[n][s-n] covers the case where you start the sequence with a 2 or more, thus you simply add 1 to every number in the sequences with sum s-n and are guaranteed to start with more than 1, the remaining DP2[n-1][s-1] covers the case where you start with exactly 1. You used a number and took 1 from the total sum, hence n-1 and s-1. The answer will be at DP2[1][S]+DP2[2][S]+..DP[S][S], but we're not actually interested in that. Our goal is to use this new dp to somehow fill an early row in our first dp and then to continue with that one towards the solution.

Combining the solutions and finishing our journey

  We noticed long ago that DP[x][s] has very few numbers in its sequences for x larger than sqrt(S), so we want to calculate the entire row of DP[sqrt(S)+1] using DP2. Say we have calculated DP2 for a certain row r. They count the number of sequences starting with 1 or more, but if we add sqrt(S) to every number in it