#P4807. 車

    ID: 3924 传统题 1000ms 128MiB 尝试: 391 已通过: 136 难度: 5 上传者: 标签>CF1800普及+/提高-双射计数线性筛质因数指数约分高精度乘法同余的加减乘运算ByFancyCoder

車

题目描述

众所周知,車是中国象棋中最厉害的一子之一,它能吃到同一行或同一列中的其他棋子。車跟車显然不能在一起打起来,于是 rly 一天又借来了许多许多的車在棋盘上摆了起来……

他想知道,在 n×mn\times m 的矩形方格中摆最多个数的車使其互不吃到的情况下方案数有几种。但是,由于上次摆炮摆得实在太累,他为了偷懒,打算增加一个条件:

对于任何一个車 aa,如果有其他一个車 bb 在它的上面(車 bb 行号小于車 aa ),那么車 aa 必须在車 bb 的右边(車 aa 列号大于車 bb)。

棋子都是相同的。

输入格式

一行,两个正整数 nn 和 mm。

输出格式

一行,输出方案数的末尾 5050 位(不足则直接输出)。

样例输入

2 2

样例输出

1

数据范围与约定

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

题目来源

By FancyCoder