1. **Problem statement:** Given a positive integer $n$, find the number of strictly increasing sequences of positive integers whose sum is $n$. 2. **Understanding the problem:** We want to count sequences $a_1 < a_2 < \cdots < a_k$ with $a_i \in \mathbb{Z}^+$ and $\sum_{i=1}^k a_i = n$. 3. **Key insight:** This is equivalent to counting partitions of $n$ into distinct parts. 4. **Formula and approach:** Let $dp[n][k]$ be the number of strictly increasing sequences summing to $n$ with largest element $k$. The recurrence is: $$ dp[n][k] = dp[n-k][k-1] + dp[n][k-1] $$ with base cases: - $dp[0][k] = 1$ for all $k \ge 0$ (empty sum) - $dp[n][0] = 0$ for $n > 0$ 5. **Explanation:** - $dp[n-k][k-1]$ counts sequences that include $k$ as the largest element. - $dp[n][k-1]$ counts sequences that do not include $k$. 6. **Final answer:** The number of strictly increasing sequences summing to $n$ is $dp[n][n]$ modulo 123456789. 7. **Example:** For $n=5$, the sequences are: - $5$ - $1+4$ - $2+3$ Total 3 sequences. 8. **Summary:** Use dynamic programming with the above recurrence to compute results for all $n$ up to 5000 efficiently. **Answer for sample inputs:** - For $n=5$, output is 3. - For $n=8$, output is 6.