#P6765. [2019备战noi]贪婪人

    ID: 6585 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>组合数学动态规划贪心CF2300数学模运算计数DP

[2019备战noi]贪婪人

贪婪人

题目描述

有一个 HH 行 WW 列的网格,每个格子具有一个整数权值。

Antetokunompo 要从左上角 (1,1)(1,1) 走到右下角 (H,W)(H,W),每次只能向下或向右移动。他按以下规则确定路线:

  • 若右侧和下侧都有格子,选择权值较大的格子;权值相同时向右走。
  • 若已到达最下行或最右列,就沿唯一可行方向走向终点。

一条路径的权值为沿途经过的所有格子的权值之和,包含起点和终点。

已知左上角格子的权值为 00,其余格子的权值均为 [0,S][0,S] 中的整数。求有多少种不同的网格赋值,使按上述规则走出的路径权值恰好为 SS。

只要某个格子的权值不同,就视为不同网格。答案对 1000710007 取模。

输入格式

输入一行三个整数 H,W,SH,W,S。

输出格式

输出一行一个整数,表示合法网格数对 1000710007 取模的结果。

样例输入

2 2 1

样例输出

4

样例解释

用三元组依次表示右上、左下、右下格子的权值,四种合法赋值为

(0,0,1),(1,0,0),(0,1,0),(1,1,0).(0,0,1),\quad(1,0,0),\quad(0,1,0),\quad(1,1,0).

数据范围

所有数据满足 1≤H,W≤25001\le H,W\le2500,0≤S≤1000\le S\le100。

70%70\% 的数据满足 H,W≤100H,W\le100。