Patrulha discreta

Time limit: 3000 msMemory limit: 256 MB

Uma estrada possui $M$ posições possíveis para postos de patrulha, numeradas de $1$ a $M$ . Existem $n$ trechos que precisam de atendimento. O trecho $i$ vai da posição $l_i$ à posição $r_i$ , incluindo os extremos.

Queremos escolher exatamente $K$ posições distintas para instalar postos, de modo que cada trecho contenha pelo menos um posto. Um mesmo posto pode atender vários trechos. Conte os conjuntos de posições possíveis, módulo $998244353$ .

Input

A primeira linha contém $n,M,K$ ( $0\le n\le3000$ ; $1\le M\le10^9$ ; ). Cada uma das próximas linhas contém , com . Trechos repetidos são permitidos. É possível que .

Output

Imprima a quantidade de conjuntos válidos módulo $998244353$ .

Samples

Sample 1

Input

2 5 2
1 2
4 5

Output

Escolha uma posição entre 1 e 2 e outra entre 4 e 5.

Sample 2

Input

0 4 2

Output

Sem trechos obrigatórios, qualquer par de posições serve.

Sample 3

Input

1 3 0
1 3

Output

Nenhum trecho não vazio pode ser atendido sem postos.