#1157. zxh的恰饭之旅

Sheauhaw 决定去吃海底捞！但是怎么才能到达呢？

Sheauhaw 在兴庆宫门口买了一份西安市地图, 上面印着学校的位置和他要去的海底捞的位置, 海底捞在学校的东北方向, 而且还有许多路线可供选择. 具体来说, 整个地图是一个街道组成的网格, 学校在 $(0,0)$ 的位置, 海底捞在 $(n,m)$ 的位置, 其中 $\vec x$ 和 $\vec y$ 分别是正东和正北方向, $n,m$ 都是非负整数.

而家 Sheauhaw 有 $k$ 种交通工具可供选择, 这些交通工具只可以在街道上走，即可以且只能沿坐标轴平行方向走, 第 $i$ 个交通工具可以一次性向前走 $a_i$ 个单位. 显然, 走回头路是很不划算的, 会延误吃饭 (约会) 的进程, Sheauhaw 决定只向正东或向正北走.

在理想状态下, 每种交通工具都可以被使用任意多次. Sheauhaw 想知道, 在这种理想状态下, 他有多少种 交通工具+方向 的排列可以到达海底捞. 答案可能非常大, 请你输出模 $919,260,817$ 的结果.

第一行三个整数 $n,m,k$, 分别表示目标位置的坐标和交通工具的选择数.

第二行 $k$ 个整数 $a_1,a_2,\cdots,a_k$, 表示交通工具各自的单次移动单位数.

一行一个整数 $A$, 表示排列数量模 $919,260,817$ 的结果.

样例输入

2 0 2
1 2

样例输出

2

$0\le n,m\le10^5$

$0<n\times m\le10^5$

$0<k\le50$

$0<a_1,a_2,\cdots,a_k\le10^{18}$

提示: 直接开 $10^5\times10^5$ 的二维数组可能会导致 CE 或 MLE.