この問題の制約下において \(10^{100}\) は \(0+1+\cdots+N\) に比べて非常に大きい数であるため、実際には次のような問題を考えるのと同じことになります：

• \(M\) を \(K\) 以上 \(N+1\) 以下の整数とする。\(0,1,\cdots,N\) から相異なる \(M\) 個の数を選びその総和を \(S\) としたとき、組 \((M,S)\) としてあり得るものの個数を求めよ。

　\(M\) を固定したとき \(S\) としてあり得るものの個数を \(f(M)\) とおき、これを求めましょう。明らかに以下の不等式が成り立ちます。 \[0+1+\cdots+(M-1)\leq S\leq (N-M+1)+\cdots+(N-1)+N\] 　\(S\) としてこの範囲の任意の整数が実現できることを示すには、\(M\) 個の数の選び方として以下のようなプロセスを踏めばよいです。

1. まず \(0,1,\cdots,M-1\) を選ぶ。
2. \(M-1\) を \(1\) ずつ増やし、\(N\) に到達したら停止する。
3. \(M-2\) を \(1\) ずつ増やし、\(N-1\) に到達したら停止する。
4. 同様に続け、最後は \(0\) を \(1\) ずつ増やし、\(N-M+1\) に到達したら停止する。

　このプロセスの任意の段階において、得られる \(M\) 個の数に重複はないことは明らかで、\(S\) は常に \(1\) ずつ増加するため求める結論が得られました。ここから \(f(M)\) の値を計算すると以下のようになります。ここで総和公式を用いても良いですが、以下のように少し工夫をすることも出来ます。

\[\begin{aligned} f(M)&=\left((N-M+1)+\cdots+(N-1)+N\right)-\left(0+1+\cdots+(M-1)\right)+1 \\ &= ((N-M+1)-0)+((N-M+2)-1)\cdots+((N-1)-(M-2))+(N-(M-1))+1 \\ &= M(N-M+1)+1 \end{aligned}\]

　これを各 \(M\) ごとに愚直に足し合わせることで \(O(N)\) で解くことも出来ますが、さらに総和公式を用いて計算を進めれば1本の式で答えを記述することもできます。具体的には、以下のようになります。 \[\sum_{M=K}^{N+1}f(M)=\frac{1}{6}(N-K+2)(N^2+NK-2K^2+N+2K+6)\]

C++ (with ACL) による実装例はこちら。