# D. Rescue Nibel! SOLUTION Codeforces Round #672 (Div. 2)

Page Contents

## Rescue Nibel! SOLUTION

Ori and Sein have beaten numerous troublesome difficulties. They at long last lit the Shrouded Lantern and discovered Gumon Seal, the way in to the Forlorn Ruins. At the point when they attempted to make the way for the remnants… nothing occurred.

Ori was exceptionally astonished, however Sein gave the clarification rapidly: smart Gumon chose to make an extra guard for the entryway.

There are n lights with Spirit Tree’s light. Sein knows the hour of turning on and off for the I-th light — li and ri separately. To open the entryway you need to pick k lights so that there will be a snapshot of time when they all will be turned on.

While Sein chooses which of the k lights to pick, Ori is intrigued: what number of ways there are to pick such k lights that the entryway will open? It might happen that Sein might not be right and there are no such k lights. The appropriate response may be enormous, so print it modulo 998244353.

Info

First line contains two numbers n and k (1≤n≤3⋅105, 1≤k≤n) — absolute number of lights and the quantity of lights that must be turned on all the while.

Next n lines contain two numbers li ans ri (1≤li≤ri≤109) — timeframe when I-th light is turned on.

Yield

Print one whole number — the response to the assignment modulo 998244353.

Models

inputCopy

7 3

1 7

3 8

4 5

6 7

1 3

5 10

8 9

outputCopy

inputCopy

3 1

outputCopy

inputCopy

3 2

outputCopy

inputCopy

1 3

2 3

outputCopy

inputCopy

5 2

1 3

2 4

3 5

4 6

5 7

outputCopy

Note

In first experiment there are nine arrangements of k lights: (1,2,3), (1,2,4), (1,2,5), (1,2,6), (1,3,6), (1,4,6), (2,3,6), (2,4,6), (2,6,7).

In second experiment k=1, so the appropriate response is 3.

In third experiment there are no such matches of lights.

In forward experiment all lights are turned on in a period 3, so the appropriate response is 1.

In fifth experiment there are seven arrangements of k lights: (1,2), (1,3), (2,3), (2,4), (3,4), (3,5), (4,5).