题号：NC21630
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
英语要怎么学? 为什么我们英语课从小上到大却仍然讲不出一句流利的口语 ,看不懂一道普通的英文题 ?
牛牛又陷入了沉思.
充满智慧的他马上意识到了不能跟老师学,应该要自己去寻求学习英语的方法
经过一些探索，他总结了快速提升英语水平的方法
- 首先认识一些基本的单词比如abc, 学会一些基本的语句比如hello world
- 然后就是创造一个全英文的环境,让自己每天只能讲英语
一个月过后,牛牛发现自己的英文已经突飞猛进,原来改变自己的观念然后付诸行动能给人带来如此大的影响
正当他沾沾自喜的时候,他突然发现桌子上有一些数字与ABC三个字符构成的草稿.
他突然想到这是他在学习ABC的时候出的一道题.
有一个数组,由整数构成,每一个整数可以变成一个A或B或C,但是同一种数字只能变成同一个字符
数一数有多少种不同的变法能使得产生的字符串的所有子序列中包含至少一个"ABC",输出答案对100000007取模
输入描述:
第一行输入一个整数n (3 ≤ n ≤ 3000),表示数组的长度
第二行输入n 个整数ai，(1≤ ai ≤ 3000)
输出描述:
输出一个整数
示例3
输入
复制
9
7 3000 1 3000 1 3000 1 10 7
备注:
子任务1：n <= 10
子任务2：n <= 50
子任务3: n <=3000