9時間 9人 9の扉
题号:NC202895
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

    在打越 钢太郎的著名解谜游戏系列《极限脱出》的第一作《九小时九个人九扇门》中,有这样一个有趣的设定:游戏中,位主人公被困在一座大型的豪华巨轮中,每个人手上都有一个奇怪的手表,手表上有一个数字,个人的数字分别是;在巨轮中,还有很多紧闭的数字门,每扇数字门上也有一个的数字,要想打开数字门逃出生天,主角们必须要满足一个奇怪的条件:

    个人能够打开门上数字为的一扇数字门,当且仅当这个人的腕表数字之和的数字根恰好为

    一个数字的数字根是指:将该数字各数位上的数字相加得到一个新的数,直到得到的数字小于为止,例如,的数字根为,故的数字根为。我们约定,小于的数字,其数字根就为其本身。

    因此,如果游戏中的一宫(手表数字为)、四叶(手表数字为)、八代(手表数字为)三人组合在一起,就可以打开编号为的数字门,这是因为,而的数字根为

    现在,你是游戏的主角,淳平,你知道船上包括自己在内的个人的手表数字,为了分析局势,你想要计算出可以打开号门的人物组合有多少种,你可以完成这项任务吗?

输入描述:

输入的第一行包含一个整数,主人公的数量。

下面一行个数,第个数字表示第位主人公的腕表数字。

输出描述:

你需要输出个数字,第个数字表示有多少种不同的人物组合,可以打开编号为的数字门。

答案可能很大,请你将答案对取模后输出。

示例1

输入

复制
9
1 2 3 4 5 6 7 8 9

输出

复制
56 56 58 56 56 58 56 56 59