路过的大佬帮忙看下，
悬赏全部作品点赞！！！说到做到！！！
基因计数（加强版）
时间限制：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救救蒟蒻吧！
悬赏：
我会给正确回答者的所有作品点赞！！！
C++，C语言
提问于7天前
3000
