题目描述

你来到了深邃巢穴的温泉（Deepnest Spring）处，见到了奎若。他给你出了一道DS题：

题目描述

你有一 $n$ 个数的序列 a_{1\dots n}，一开始为全 $0$。你有一个变量 $x$，一开始也为 $0$。

给定 $q$ 次询问，每次询问形如：

1 l r v，表示对所有 $l\le i\le r,a_i\leftarrow\max(a_i,v)$。

2 l r v，表示对所有 $l\le i\le r,a_i\leftarrow\min(a_i,v)$。

3 l r，表示对所有 $l\le i\le r,x\leftarrow x+a_i$。

输出 $x\text{mod}10^9+7$。

因为你不纯粹，所以你思考了一会儿就会了这个题。你开始想一个别的问题：

给定 $n,m,q$，奎若给的题有 $\frac{n(n+1)}{2}(2m+1)^q$ 种合法输入。求出这些输入对应的输出之和对 $10^9+7$ 取模的值。

输入格式

一行三个数$n,m,q$ 。

输出格式

一行一个数，表示答案。

样例1输入

1 2 3

样例1输出

13

数据范围

$1\le n,m,q\le 2\times 10^5$。