Ograda

Nakon što je za velike pare prodao svoju aplikaciju jednoj poznatoj svjetskoj IT tvrtci, Matej je na obroncima Bilogore sagradio dvorac. Jedan dio zemljište oko dvorca ogradio je ogradom duljine N metara. Kako jako voli boje, a postavljena ograda je bila bijela, odlučio je ogradu obojati koristeći K boja koje je našao u dvorcu. Kako bi bojanje bilo zanimljivije, za neke dijelove ograde zadao je s koliko različitih boja u tom dijelu ograda smije biti obojana. Svaki metar ograde obojat će u jednu od K boja, a u snu mu se pojavilo Q uvjeta, „Od L-itog do R-tog metra smije se nalaziti najviše Xi različitih boja”. Napišite program koji će za zadane ulazne podatke ispisati na koliko se načina može obojati cijela ograda.

Ulazni podatci

U prvom su retku prirodni brojevi N, K i cijeli broj Q, brojevi iz teksta zadatka. U sljedećih Q redaka nalaze se brojevi Li , Ri , Xi (1 ≤ Li ≤ Ri ≤ N, 0 ≤ Xi ≤ K).

Izlazni podatci

U jedini redak ispišite traženi broj modulo 998244353.

Bodovanje

Podzadatak Bodovi Ograničenja

1 6 1 ≤ N, K ≤ 4, 0 ≤ Q ≤ 20 2 17 1 ≤ N, K ≤ 11, 0 ≤ Q ≤ 20 3 37 1 ≤ N, K ≤ 21, 0 ≤ Q ≤ 20

Probni primjeri

ulaz ulaz

3 6 1 4 3 2 1 2 1 1 2 1 2 4 2 izlaz izlaz 36 21

Pojašnjenje prvog probnog primjera: Matej može prva dva metra obojati u bilo koju od 6 boja te zadnji metar u bilo koju od 6 boja, time ukupno dobivši 36 mogućnosti.