20170105 - 基因组分析

通过次数

28

提交次数

75

Time Limit : 1 秒
Memory Limit : 128 MB

乌龟得到了他的基因组,一个只包含“ATCG”四种字母的字符串。乌龟想起科学家说,基因组中很多片段都多次重复出现,而且这种重复是很有意义的,于是他想计算一下自己基因组里片段的重复情况。给定一个基因组,其中一个长度为k 的子串称为一个“k-片段”。乌龟希望你计算出基因组中不同的k-片段数量。例如,基因组“TACAC” 的2-片段有“TA”,“AC”, “CA”, “AC”,其中不同的片段数量有3 个。

Input

整数n, k, R1,表示基因组的长度、片段的长度和数列生成的首项。基因组第i (1 i n) 个字符在Ri mod 4 的值为0, 1, 2, 3 时分别为A, T, C, G

Output

一个整数,表示不同的k-片段的数量

Examples

Input

20 2 37

Output

10

Hint

数据规模

30% 的数据满足n<=100;

100%的数据满足1<=n<=10^5, 1<=k<= 10

Source

2017 年江苏省信息与未来夏令营