Cabos sem cruzamentos

Time limit: 4000 msMemory limit: 256 MB

Há $n$ terminais em pontos distintos de uma circunferência, numerados de $1$ a $n$ em ordem no sentido horário. Uma lista informa os $m$ pares de terminais que podem ser ligados por cabos. Cada cabo é o segmento de reta entre seus dois terminais.

Uma rede válida escolhe exatamente $n-1$ cabos da lista, conecta todos os terminais e não tem cruzamentos: dois cabos podem compartilhar um terminal, mas seus interiores não podem se intersectar.

Conte quantas redes válidas existem. Redes são diferentes quando seus conjuntos de cabos são diferentes. As coordenadas dos terminais não são fornecidas, pois apenas sua ordem ao redor da circunferência importa.

Input

A primeira linha contém $n$ e $m$ ( $2\le n\le 400$ , $0\le m\le n(n-1)/2$ ). Cada uma das próximas linhas contém dois inteiros e (), indicando um cabo permitido. Não há pares repetidos. A lista não precisa permitir conectar todos os terminais.

Output

Imprima o número de redes válidas módulo $998244353$ .

Samples

Sample 1

Input

Output

Qualquer escolha de dois dos três cabos é válida.

Sample 2

Input

Output

Os três cabos seriam necessários para conectar todos os terminais, mas $(1,3)$ e $(2,4)$ se cruzam.

Sample 3

Input

Output

Existem 16 árvores com esses quatro terminais e todos os pares permitidos. Exatamente quatro contêm os dois cabos que se cruzam, restando 12 redes válidas.