### Problem Statement : here

The tricky part is the addition of 10^100. So, let us assume that we are using k numbers to generate our sum. Clearly, in this case, the coefficient of 10^100 will be k. If we would have used k+1 terms, the coefficient would have differed and this makes the two numbers different. So the cases like 1+ 8 = 3+5+1 are not possible, because each of them has different coefficients of 10^100.

So, what we are left with?

Given k -> number of terms, what are the possible values of the sum I can get?

So, if I calculate the minimum possible sum and the maximum possible sum, then I claim that we can get any number in between this sum range. It is a well-known fact. So, we use it in order to solve this question. The proof – intuitive that can be taken to convince is :

min-sum = 0 + 1 + 2 + 3 ………. + k-1

max-sum = n-(k-1) + n-(k-2) + n-(k-3) + ……. + n

To get any sum in this range, we can start distributing the difference between given value and min-sum to 0 (until it becomes n-(k-1)), remaining to 1 and so on up to k-1 (until it becomes n).

ll modp(ll a, ll b){ ll res = 1; while(b>0){ if (b&1) res = (res*a)%M1; a = (a*a)%M1; b>>=1; } return res; } ll minsum[200005]; void solve() { ll n,k; cin>>n>>k; minsum[1] = 0; ll maxsum = (((n*(n+1))%M1)*modp(2,M1-2))%M1; rep(i,2,n+2){ minsum[i] = (minsum[i-1] + i-1 + M1)%M1; } ll ans = 0; rep(i,k,n+2){ ans = (ans + maxsum - minsum[n-i + 1] - minsum[i] + 1 + M1)%M1; } cout << ans << endl; }