题解

这是道比较经典的线性DP问题，当前的决策与上次决策有关，是 打家劫舍 的变形题

定义 $dp[i][j]$ 表示，当前考虑到第 $i$ 个数，且上一次选的字母是 $j$ 的所有合法方案数。

状态转移为： $dp[i][j] = \sum_{k \neq j} dp[i-1][k]$。

即前 $i$ 天选择字符 $j$ 对应商家的方案数,等于前 $i-1$ 天选择除 $j$ 以外任意字符的方案数之和。

题目描述

小美经常去美团上点外卖，她给自己规划了每天会在哪些商家中选择一家来点。

由于怕吃腻，小美决定不会连续两天点同一个商家。现在请你判断小美有多少种不同的选择方案？

输入描述

第一行输入一个正整数$n$，代表小美点外卖的天数。

接下来的$n$行，每行输入一个长度不超过20的字符串，代表小美每天的选项。相同的字符代表同一个商家。

$1\le n\le 10^5$

保证每个字符串内的字符都不同。

输出描述

输出一个整数，代表小美点外卖的方案数。由于答案过大，请对$10^9+7$取模

样例

输入

2
ab
bcd

输出

5

说明

方案 1：第一天点商家 a，第二天点商家 b。
方案 2：第一天点商家 a，第二天点商家 c。
方案 3：第一天点商家 a，第二天点商家 d。
方案 4：第一天点商家 b，第二天点商家 c。
方案 5：第一天点商家 b，第二天点商家 d。