U726161 限额最短路

【本题已于9月7日12:40补充7组更强样例】 【本题已于9月7日16:10修改时空限制为4s 512MB，与QOJ保持一致，受洛谷限制无法设置为1024MB】 【本题已于9月7日16:30补充n=1的样例】

给定一张包含 $n$ 个点、$m$ 条边的有向图。所有边的边权均为 $1$，第 $i$ 个点有非负点权 $c_i$。 一条路径的**长度**定义为经过的边数，一条路径的**点权和**定义为路径上所有点（包含起点和终点）的点权之和。 请在所有从点 $1$ 到点 $n$ 的最短路径中，统计点权和不超过 $C$ 的路径条数。答案对 $2^{64}$ 取模。 图中没有重边，也没有自环。

第一行输入三个整数 $n,m,C$。 第二行输入 $n$ 个整数 $c_1,c_2,\ldots,c_n$。 接下来 $m$ 行，每行输入两个整数 $u,v$，表示一条从 $u$ 指向 $v$、边权为 $1$ 的有向边。

输出一个整数，表示满足条件的路径数对 $2^{64}$ 取模后的结果。输出应位于 $[0,2^{64}-1]$ 内。

从点 $1$ 到点 $4$ 的最短路径都恰好经过两条边，分别为 $1\to2\to4$ 和 $1\to3\to4$。它们的点权和分别为 $7$ 和 $8$，均不超过 $C=8$。 路径 $1\to2\to3\to4$ 不是最短路径，因此不计入答案。 对于所有数据： $$ 1\le n\le 90,\qquad 0\le m\le 300,\qquad 0\le C\le 10^{12}, $$ $$ 0\le c_i\le 10^{12}. $$ 若点 $n$ 从点 $1$ 不可达，答案为 $0$。 答案模数恰为 $2^{64}$。在 C++ 中可以使用 `uint64_t` 的自然溢出完成取模。