Statement

You are given an integer N and the following undirected graph: (1) The graph contains N nodes, which are numbered from 1 to N. (2) There exists an undirected edge between two nodes U and V (1 < U,V < N) if and only if 1 < |U-V| < 2. There are M distinct forbidden edges (U_i,V_i) (i = 0, …, M - 1). Find the number of simple paths in this graph from node 1 to node N that do not contain any of the M forbidden edges. Since the answer can be very large, print its remainder modulo 998244353. A simple path is a sequence of pairwise distinct nodes u_1,u_2,…,u_k such that u_i and u_i+1 are connected by an edge in the graph, for all 1 < i < k.