Input: $[X,Y]$ and $L$
Output : no of increasing sequence of length L and all elements should be $X\le i \le Y$ e.g: for $[6,7]$ and $2$ sequences are $6,66,67,7,77.$
For the above question my answer is the following sequence
$a+b+c+d+..$ where
$a=N$
$b=\sum_{i=1}^{N} i$
$c = \sum_{i=1}^{N}\sum_{j=1}^{i} j $
$d = \sum_{i=1}^{N}\sum_{j=1}^{i}\sum_{k=1}^{j} k$
$...$ and the no of elements in the sequence is $D = Y-X +1$
is there any formula to the above sequence?
Edit :
For the above I found that multiset is answer. Then again I encountered other issues.
how to efficiently calculate
$\sum_{k=1}^{D} {n+k-1 \choose k}$ mod 10^6+3, $1\le n,D\le 10^9$?
Notice that $${n \choose m}={n-1 \choose m-1}+{n-1 \choose m}$$
Hence \begin{align*} \sum_{k=1}^{D} {n+k-1 \choose k} &= \sum_{k=1}^{D} {n+k-1 \choose n-1} \\ &= {n \choose n} + \sum_{k=1}^{D} {n+k-1 \choose n-1} - {n \choose n} \\ &= {n \choose n} + {n+1-1 \choose n-1}+ \cdots +{n+D-1 \choose n-1} - {n \choose n} \\ &= {n+1 \choose n} + {n+2-1 \choose n-1} +\cdots +{n+D-1 \choose n-1} - {n \choose n} \\ &= {n+2 \choose n} + {n+3-1 \choose n-1} +\cdots +{n+D-1 \choose n-1} - {n \choose n} \\ &= \cdots\\ &= {n+D \choose n}-1 \end{align*}
Use Lucas' theorem to compute it for $1\le n,D\le 10^9$ (notice that $10^6+3$ is a prime number).