Sheauhaw 决定去吃海底捞!但是怎么才能到达呢?
Sheauhaw 在兴庆宫门口买了一份西安市地图, 上面印着学校的位置和他要去的海底捞的位置, 海底捞在学校的东北方向, 而且还有许多路线可供选择. 具体来说, 整个地图是一个街道组成的网格, 学校在 的位置, 海底捞在 的位置, 其中 和 分别是正东和正北方向, 都是非负整数.
而家 Sheauhaw 有 种交通工具可供选择, 这些交通工具只可以在街道上走,即可以且只能沿坐标轴平行方向走, 第 个交通工具可以一次性向前走 个单位. 显然, 走回头路是很不划算的, 会延误吃饭 (约会) 的进程, Sheauhaw 决定只向正东或向正北走.
在理想状态下, 每种交通工具都可以被使用任意多次. Sheauhaw 想知道, 在这种理想状态下, 他有多少种 交通工具+方向 的排列可以到达海底捞. 答案可能非常大, 请你输出模 的结果.