题目内容

在一棵有 $n$ 个节点的树上，节点编号为 $1$ 到 $n$，每个节点有一个正整数的评分 $a_i$。定义树上的一个点集 $S$ 为“连通点集”，当且仅当对于 $S$ 中任意两个节点 $u$ 和 $v$，从 $u$ 到 $v$ 的简单路径上所有节点都属于 $S$。特别地，只包含一个节点的集合也算作连通点集。

如果一个连通点集中所有节点评分的乘积能被 $10$ 整除（即乘积的十进制表示末尾至少有一个 $0$），则称该连通点集为“幸运集”。请你计算树上幸运集的总数。由于答案可能很大，需要对 $10^9+7$ 取模。

节点数 $n$ 不超过 $10^5$，每个节点的评分 $a_i$ 均为正整数且不超过 $10^9$。

输入描述

第一行包含一个整数 $n$，表示树的节点数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个节点的评分。