路过的大佬帮忙看下，

悬赏10元私信红包！！！
救救蒟蒻吧！！！
基因计数（加强版）
时间限制：1.0s 内存限制：256.0MB
问题描述
　　给定一个碱基序列，问长度为L的包含这段碱基序列的基因有多少种？注意基因只由A、T、G、C四种碱基组成，如果表达出来不同，则认为是不同的基因。
输入格式
　　输入的第一行包含一个字符串，表示给定的碱基序列。
　　第二行包含一个整数L。
输出格式
　　输出一个整数，表示答案对123456789取余的结果。
样例输入
ATAT
6
样例输出
47
数据规模和约定
　　对于10%的评测用例，1 ≤ 字符串长度 ≤ 10， 1 ≤ L ≤ 10。
　　对于20%的评测用例，1 ≤ 字符串长度 ≤ 10， 1 ≤ L ≤ 100。
　　对于50%的评测用例，1 ≤ 字符串长度 ≤ 100， 1 ≤ L ≤ 10000。
　　对于100%的评测用例，1 ≤ 字符串长度 ≤ 100， 1 ≤ L ≤ 10^18。

麻了，请各位dalao救救蒟蒻吧！
悬赏：

我会给正确回答者私信10元红包！！！