#P6765. [2019备战noi]贪婪人
[2019备战noi]贪婪人
贪婪人
题目描述
有一个 行 列的网格,每个格子具有一个整数权值。
Antetokunompo 要从左上角 走到右下角 ,每次只能向下或向右移动。他按以下规则确定路线:
- 若右侧和下侧都有格子,选择权值较大的格子;权值相同时向右走。
- 若已到达最下行或最右列,就沿唯一可行方向走向终点。
一条路径的权值为沿途经过的所有格子的权值之和,包含起点和终点。
已知左上角格子的权值为 ,其余格子的权值均为 中的整数。求有多少种不同的网格赋值,使按上述规则走出的路径权值恰好为 。
只要某个格子的权值不同,就视为不同网格。答案对 取模。
输入格式
输入一行三个整数 。
输出格式
输出一行一个整数,表示合法网格数对 取模的结果。
样例输入
2 2 1
样例输出
4
样例解释
用三元组依次表示右上、左下、右下格子的权值,四种合法赋值为
数据范围
所有数据满足 ,。
的数据满足 。