using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("10");
WillReturn.Add("1 2 3 4");
WillReturn.Add("2 -1 -1 5");
WillReturn.Add("3 -1 -1 7");
WillReturn.Add("4 5 8 9");
//2
}
else if (InputPattern == "Input2") {
WillReturn.Add("30");
WillReturn.Add("1 1 -1 -1");
WillReturn.Add("-1 -1 -1 -1");
WillReturn.Add("-1 -1 -1 -1");
WillReturn.Add("-1 -1 -1 -1");
//0
}
else if (InputPattern == "Input3") {
WillReturn.Add("21");
WillReturn.Add("-1 -1 -1 -1");
WillReturn.Add("-1 -1 -1 -1");
WillReturn.Add("-1 -1 -1 -1");
WillReturn.Add("-1 -1 -1 -1");
//248851853
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
}
const long Hou = 998244353;
static long[,] mBanArr;
static void Main()
{
List<string> InputList = GetInputList();
long M = long.Parse(InputList[0]);
mBanArr = CreateBanArr(InputList.Skip(1));
// 場合の数[状態]なDP表
var PrevDP = new Dictionary<long, long>();
JyoutaiDef FirstJyoutai;
long Val_0_0 = GetBanVal(0);
if (Val_0_0 == -1) {
for (long I = 1; I <= M; I++) {
FirstJyoutai.CurrVal = I;
FirstJyoutai.Prev1Val = 0;
FirstJyoutai.Prev2Val = 0;
FirstJyoutai.Prev3Val = 0;
PrevDP[GetHash(FirstJyoutai)] = 1;
}
}
else {
FirstJyoutai.CurrVal = Val_0_0;
FirstJyoutai.Prev1Val = 0;
FirstJyoutai.Prev2Val = 0;
FirstJyoutai.Prev3Val = 0;
PrevDP[GetHash(FirstJyoutai)] = 1;
}
for (long I = 1; I <= 15; I++) {
var CurrDP = new Dictionary<long, long>();
foreach (var EachPair in PrevDP) {
JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);
// 使用する値の候補
var KouhoSet = new HashSet<long>();
long BanVal = GetBanVal(I);
if (BanVal != -1) {
KouhoSet.Add(BanVal);
}
else {
for (long J = 1; J <= M; J++) {
KouhoSet.Add(J);
}
}
foreach (long EachKouho in KouhoSet.ToArray()) {
bool IsOK = false;
if (I % 4 >= 1) {
if (CurrJyoutai.CurrVal < EachKouho && CurrJyoutai.Prev3Val < EachKouho) {
IsOK = true;
}
}
else {
if (CurrJyoutai.Prev3Val < EachKouho) {
IsOK = true;
}
}
if (IsOK == false) {
KouhoSet.Remove(EachKouho);
}
}
foreach (long EachKouho in KouhoSet) {
JyoutaiDef NewJyoutai;
NewJyoutai.CurrVal = EachKouho;
NewJyoutai.Prev1Val = CurrJyoutai.CurrVal;
NewJyoutai.Prev2Val = CurrJyoutai.Prev1Val;
NewJyoutai.Prev3Val = CurrJyoutai.Prev2Val;
long NewHash = GetHash(NewJyoutai);
if (CurrDP.ContainsKey(NewHash) == false) {
CurrDP[NewHash] = 0;
}
CurrDP[NewHash] += EachPair.Value;
CurrDP[NewHash] %= Hou;
}
}
PrevDP = CurrDP;
}
long Answer = 0;
foreach (long EachVal in PrevDP.Values) {
Answer += EachVal;
Answer %= Hou;
}
Console.WriteLine(Answer);
}
struct JyoutaiDef
{
internal long CurrVal; // 現在マスの値
internal long Prev1Val; // 1つ前の値
internal long Prev2Val; // 2つ前の値
internal long Prev3Val; // 3つ前の値
}
// 位置番号を引数として、盤面の値を返す
static long GetBanVal(long pInd)
{
if (pInd == 0) return mBanArr[0, 0];
if (pInd == 1) return mBanArr[1, 0];
if (pInd == 2) return mBanArr[2, 0];
if (pInd == 3) return mBanArr[3, 0];
if (pInd == 4) return mBanArr[0, 1];
if (pInd == 5) return mBanArr[1, 1];
if (pInd == 6) return mBanArr[2, 1];
if (pInd == 7) return mBanArr[3, 1];
if (pInd == 8) return mBanArr[0, 2];
if (pInd == 9) return mBanArr[1, 2];
if (pInd == 10) return mBanArr[2, 2];
if (pInd == 11) return mBanArr[3, 2];
if (pInd == 12) return mBanArr[0, 3];
if (pInd == 13) return mBanArr[1, 3];
if (pInd == 14) return mBanArr[2, 3];
if (pInd == 15) return mBanArr[3, 3];
return long.MinValue;
}
static JyoutaiDef GetJyoutai(long pHash)
{
JyoutaiDef WillReturn;
WillReturn.Prev3Val = pHash % 100; pHash /= 100;
WillReturn.Prev2Val = pHash % 100; pHash /= 100;
WillReturn.Prev1Val = pHash % 100; pHash /= 100;
WillReturn.CurrVal = pHash % 100;
return WillReturn;
}
static long GetHash(JyoutaiDef pJyoutai)
{
long Hash = 0;
Hash += pJyoutai.CurrVal; Hash *= 100;
Hash += pJyoutai.Prev1Val; Hash *= 100;
Hash += pJyoutai.Prev2Val; Hash *= 100;
Hash += pJyoutai.Prev3Val;
return Hash;
}
////////////////////////////////////////////////////////////////
// IEnumerable<string>をlongの2次元配列に設定
////////////////////////////////////////////////////////////////
static long[,] CreateBanArr(IEnumerable<string> pStrEnum)
{
var StrList = new List<string>(pStrEnum);
if (StrList.Count == 0) {
return new long[0, 0];
}
long[] LongArr = { };
Action<string> SplitAct = pStr =>
LongArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
SplitAct(StrList[0]);
long UB_X = LongArr.GetUpperBound(0);
long UB_Y = StrList.Count - 1;
long[,] WillReturn = new long[UB_X + 1, UB_Y + 1];
for (long Y = 0; Y <= UB_Y; Y++) {
SplitAct(StrList[(int)Y]);
for (long X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = LongArr[X];
}
}
return WillReturn;
}
}