Electrician
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

NIO would like to be an electrician.

He is now confronted with a difficult task. The device he is working on has a circular frame and there are N equidistant vertices on the frame. It can be simplified to a circle on a two-dimensional plane. In addition to the outermost circular frame, there are also vertices on the frame. It can be simplified to a circle on a two-dimensional plane. In addition to the outermost circular frame, there are also M holders inside which can be simplified to segments connecting the vertices on the circle. Because these holders are produced together, they are all the same "length" L. "Length" L means that if a segment start at i-th vertex, it would end at -th vertex and i must satisfy .

The task is to place two wires on the frame, one from vertex 1 to N and another from 2 to N-1. The wires must be close to the segments or arcs on the frame and on where two segments intersect, a wire can also be connected from one segment to another.

For safety, two wires cannot intersect at any position, that is, they can not pass through the same vertex or intersections of segments, including vertex 1, 2, For safety, two wires cannot intersect at any position, that is, they can not pass through the same vertex or intersections of segments, including vertices 1, 2, N-1 and N. And on any segment and arc, the wire must follow the direction from the vertex with the small number to the vertex with the large number.

NIO wants to know how many schemes he has for placing wires.

Since the answer is too large, NIO only wants to know it modulo 998244353..

输入描述:

The first line contains two integers N, M, L .

The following line contains M distinct integers , donating that there is a segment connecting s_i and .

输出描述:

A single non-negative integer, denoting the answer, modulo 998244353.
示例1

输入

复制
6 3 1
1 2 3

输出

复制
4
示例2

输入

复制
12 5 4
1 2 5 7 8

输出

复制
42