Рабочее место участника

Рассмотрим все `N`-элементные последовательности из целых чисел от 0 до `K-1`. Например, при `N=2` и `K=3` получаются последовательности (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1) и (2,2). Требуется определить количество последовательностей среди них, которые удовлетворяют `M` ограничениям, задаваемых тройкой чисел `(A,\ B,\ C)`: остаток от деления на `K` суммы элементов последовательности с `A`-го по `B`-ый равен `C`. Так как количество удовлетворяющих ограничениям последовательностей может быть очень большим, то нужно вывести только остаток от деления этого числа на 10000. Например, если `N=2,\ K=3` и сумма элементов с первого по второй равна 2, то удовлетворять условию будут последовательности: (0,2), (1,1) и (2,0), а если к этому добавить еще, что сумма элементов с первого по первый равна 1, то удовлетворять условиям будет только последовательность (1,1).

В первой строке входного файла содержится три целых числа `N,\ K,\ M\ (1\ ≤\ N,\ K\ ≤\ 1000,\ 0\ ≤\ M\ ≤\ 1000)`. Далее следуют `M` строк, каждая из которых содержит описание одного из ограничений, т.е. тройка целых числа `A_i,\ B_i` и `C_i\ (1\ ≤\ A_i\ ≤\ B_i\ ≤\ N,\ 0\ ≤\ C_i\ ≤\ K-1`, `i` от 1 до `M`). Все числа в строках отделены друг от друга одним пробелом.

Вывести единственное целое число, равное остатку от деления на 10000 количества удовлетворяющих ограничениям `N`-элементных последовательностей.

2 3 2
1 2 2
1 1 1

1

3 2 2
1 2 0
2 3 0

2

3 3 3
1 3 2
1 1 1
2 3 0

0