在打越 钢太郎的著名解谜游戏系列《极限脱出》的第一作《九小时九个人九扇门》中,有这样一个有趣的设定:游戏中,位主人公被困在一座大型的豪华巨轮中,每个人手上都有一个奇怪的手表,手表上有一个数字,
个人的数字分别是
;在巨轮中,还有很多紧闭的数字门,每扇数字门上也有一个
的数字,要想打开数字门逃出生天,主角们必须要满足一个奇怪的条件:
个人能够打开门上数字为
的一扇数字门,当且仅当这
个人的腕表数字之和的数字根恰好为
。
一个数字的数字根是指:将该数字各数位上的数字相加得到一个新的数,直到得到的数字小于为止,例如,
的数字根为
,故
的数字根为
。我们约定,小于
的数字,其数字根就为其本身。
因此,如果游戏中的一宫(手表数字为)、四叶(手表数字为
)、八代(手表数字为
)三人组合在一起,就可以打开编号为
的数字门,这是因为
,而
的数字根为
。
现在,你是游戏的主角,淳平,你知道船上包括自己在内的个人的手表数字,为了分析局势,你想要计算出可以打开
号门的人物组合有多少种,你可以完成这项任务吗?
输入的第一行包含一个整数
,主人公的数量。
下面一行
个数,第
个数字
表示第
位主人公的腕表数字。
你需要输出
个数字,第
个数字表示有多少种不同的人物组合,可以打开编号为
的数字门。
答案可能很大,请你将答案对
取模后输出。