路过的大佬帮忙看下，悬赏10元私信红包！！！救救蒟蒻吧！！！基因计数（加强版）时间限制：1.0s 内存限制：256.0MB问题描述　　给定一个碱基序列，问长度为L的包含这段碱基序列的基因有多少种？注意基因只由A、T、G、C四种碱基组成，如果表达出来不同，则认为是不同的基因。输入格式　　输入的第一行包含一个字符串，表示给定的碱基序列。　　第二行包含一个整数L。输出格式　　输出一个整数，表示答案对123456789取余的结果。样例输入ATAT6样例输出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元红包！！！