YOU: "How did your work for the event go?"

ZACH: "A bit rocky. Kevin originally had me on the photo booth, but the day of the event, the booth company cancelled on us."

YOU: "So what did you do?"

ZACH: "Kevin improvised. Honestly, he did a great job thinking on his feet. Instead of a booth, he had me set up a photo wall, just a trellis to hang photos on, plus a polaroid camera anyone could use."

YOU: "How did that go?"

ZACH: "Pretty smoothly, actually. Finished quick, so I got to talk to a few people around the venue."

YOU: "Anyone in particular?"

ZACH: "Mostly talked algorithms with Patrick, since he was stuck in the kitchen all night. We didn't even know anything had happened until you came in and told us."

Zach wanted to set up a photo booth for the event, but the booth company canceled on him at the last minute. His new task is to set up a photo wall instead, using photos from the past few years of ACPC.

Zach has ~n~ boxes of photos. The ~i~th box contains ~a_i~ photos with Zach in them, and ~b_i~ photos without Zach in them. Each photo is considered unique.

Because he is in a rush, Zach doesn't have time to think about all the boxes at once. Instead, he will pick two different boxes, take any number of photos from them, and stick them on the wall. Photos may be selected from one box, the other, or both.

Zach cares a lot about his publicity, and believes he will gain maximal aura if he uses exactly ~k~ photos with him in them. Zach wants to know the total count, summed over every pair of boxes he could choose, of selections containing exactly ~k~ photos of him.

Since the photos are unique, two selections are considered different if and only if they differ in which specific photos are chosen.

Input

The first line contains two integers ~n~ and ~k~ (~1 \leq n \leq 10^6~, ~0 \leq k \leq 10^6~), the number of boxes of photos Zach has, and the exact number of photos containing Zach that must be selected.

The next ~n~ lines contain two integers ~a_i~ and ~b_i~ (~0 \leq a_i, b_i \leq 10^4~), indicating that box ~i~ contains ~a_i~ photos with Zach in them and ~b_i~ photos without Zach in them. At least one of ~a_i~, ~b_i~ is greater than ~0~.

It is guaranteed that ~n \times k \leq 10^6~.

Output

Output the total number of valid photo selections, summed over all pairs of boxes, modulo ~998244353~.

Example

Input 1

3 2
0 2
2 1
1 1

Output 1

18

• If Box 1 and Box 2 are used, there are ~8~ sets of photos that contain exactly ~2~ photos of Zach.
• If Box 2 and Box 3 are used, there are ~12~ sets of photos that contain exactly ~2~ photos of Zach.
• If Box 1 and Box 3 are used, there are ~0~ sets of photos what contain exactly ~2~ photos of Zach.

Overall, there are ~18~ distinct sets of photos that contain exactly ~2~ photos of Zach.

Input 2

4 1
1 1
1 1
1 1
1 1

Output 2

32

Input 3

3 3
3 0
0 3
3 0

Output 3

34