Старший лейтенант Соколов-Орлов известен тем, что всегда умеет хорошо оценить сложность задания. Но на этот раз миссия его солдатам предстоит непростая. Им необходимо преодолеть участок, на котором расположены хитроумные ловушки.
Участок представляет собой прямоугольник NM, разбитый на квадратные поля размером 11. Благодаря работе разведки удалось выяснить, что для каждого поля с координатами (i, j) существует некий коэффициент, который равен сумме всех подряд расположенных чисел, начиная от минимального из чисел i и j, и заканчивая максимальным из них, взятой по модулю m. Солдат может прыгнуть на соседнее поле вперед или вправо, либо перепрыгнуть через одно поле в тех же направлениях. За границы участка выпрыгивать нельзя. Если же коэффициент поля, на котором находился солдат, выше коэффициента поля, на которое он приземлится, то произойдет взрыв и солдат неминуемо пострадает.
Для того чтобы оценить сложность задания, старшему лейтенанту не хватает только одного числа – количества способов, которыми солдат может попасть из поля с координатами (1, 1) в поле с координатами (N, M) целым и невредимым. Причем это число также должно быть взято по модулю m. Помогите старшему лейтенанту достойно справиться с этой задачей и получить долгожданное повышение.
Входные данные
Во входном файле записаны через пробел три числа: N, M и m (1  N, M  1000; 1  m  1000000). Считается, что в начале пути солдат находится в поле (1, 1). Прыжок на одно поле вперед означает попадание в поле (2, 1), а вправо – в поле (1, 2). Правое дальнее поле имеет координаты (N, M).
Выходные данные
В выходной файл нужно вывести одно целое число — количество способов, которыми солдат может попасть невредимым в поле (N, M), взятое по модулю m.