#P4005. [JLOI2015]骗我呢

    ID: 3206 传统题 2000ms 128MiB 尝试: 288 已通过: 137 难度: 8 上传者: 标签>CF2500提高+/省选-双射计数格路计数反射原理阶乘逆元预处理费马小定理快速幂

[JLOI2015]骗我呢

题目描述

说起来,毕业之后 B 君也就见过 R 君两面而已。

R 君有一个 n∗mn * m 的数组 xi,j(1≤i≤n;1≤j≤m)x_{i,j}(1\le i\le n; 1\le j\le m)。对于 1≤i≤n;1≤j≤m1\le i\le n; 1\le j\le m,满足 0≤xi,j≤m0\le x_{i,j}\le m。求 xi,jx_{i,j} 的解数。

B 君觉得限制太宽松,还要求对于 1≤i≤n;1≤j<m1\le i\le n; 1\le j<m,满足 xi,j<xi,j+1x_{i,j}<x_{i,j+1},对于 1<i≤n,1≤j<m1<i\le n,1\le j<m,满足 xi,j<xi−1,j+1x_{i,j}<x_{i-1,j+1}。

B 君认为 R 君可以直接 pwn 掉这个题。

R 君说:「黑的实在逼真 =.=,你起码把解数模 109+710^9+7 吧。」

B 君觉得 R 君说的有道理,于是想让你求解数模 109+710^9+7 的结果。

输入格式

一行两个整数表示 n,mn, m,含义如题目中所述。

输出格式

一行一个数表示同时满足 B 君和 R 君的条件 xi,jx_{i,j} 的解数,模 109+710^9+7 的结果。

3 3
40

数据范围

对于 100%100\% 的数据,1≤m,n≤1061\le m,n\le 10^6