DNA without a restriction site

counting string matching automaton matrix divide and conquer bioinformatics contests

A restriction enzyme cuts DNA where it meets its recognition site, a short word of the letters A, C, G, T: EcoRI cuts at GAATTC, BamHI at GGATCC. How many DNA sequences of length n exist in which the site never occurs, and which the enzyme therefore leaves alone? The sequences are any words of the letters A, C, G, T; print the answer modulo 10⁹ + 7.

The second example is the EcoRI site and the length of the phage lambda genome, 48,502 letters (NCBI RefSeq NC_001416.1).

Input

One line: n and the word w (1 ≤ n ≤ 10¹⁸, 1 ≤ |w| ≤ 15, w consists of the letters A, C, G, T).

Output

The number of sequences of length n in which w does not occur as a contiguous piece, modulo 10⁹ + 7.

Examples

Example 1

Input

3 AA

Output

Example 2

Input

48502 GAATTC

Output

394153108

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 10 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Imagine the sequence is written letter by letter, and after each letter you look: what is the longest piece of the beginning of the word now written at the end? How many possible answers are there, and what does the next letter change?

2Hint 2

For the word AAC and the text …AAA: after the third A what is written is not “nothing” but AA again. The rule “no match, go back to the start” is wrong here.

3The idea

The state is how many letters of the word match the end of the text written: from 0 to |w| − 1 (reaching |w| is not allowed, as it would mean the word has occurred). The next letter uniquely determines the new state, and the transitions are the Knuth–Morris–Pratt automaton: on a mismatch fall back along the prefix function, not to zero. A sequence of length n without the word is a walk of n transitions from state 0 that never reaches |w|. The number of such walks is the sum of the first row of Tⁿ, where T_st is how many letters lead from s to t.

4Walkthrough

The prefix function of the word, then for each state s and each letter the new state: while the letter does not continue the match, fall back k ← fail[k]; if it does, k + 1. A transition to |w| is not written into the matrix. A |w| × |w| matrix, at most 15 × 15, to the power n is fewer than 120 products modulo the prime. The answer is the sum of the first row.

A check on something small: n = 3, the word AA. There are 64 words in all, 7 of them contain AA (AAx, xAA, with AAA counted twice), which leaves 57. For EcoRI and the length of the lambda genome, the second example. A random sequence of this length almost certainly contains GAATTC about a dozen times, and sequences entirely without it make up a share of about 7·10⁻⁶ of all 4ⁿ.

4+Solution

5Complexity

O(|w|³ log n): 15³ · 120 ≈ 4·10⁵ multiplications. Brute force or dynamic programming over positions of the text, O(n·|w|), are impossible for n up to 10¹⁸, but are fine for checking on small n.

6Common mistakes

Falling back to the start. An automaton that goes to 0 on a mismatch (or to 1 if the letter matches the first one) is wrong for words whose beginning repeats inside them: GGATCC, GAGAGAC, AAC.
Inclusion–exclusion head-on. 4ⁿ − (n − |w| + 1)·4^n−|w| does not account for the word occurring several times and even overlapping.
A text shorter than the word. Then the word never occurs, and the answer is 4ⁿ.

Algorithms behind it

NUM Algorithm Matrices and recurrences A matrix power: walks of length k in a graph, linear recurrences, the transfer matrix and Markov chains. O(m³ log k) for A^k of size m × m 2 problems STR Algorithm Prefix function and KMP All occurrences of a pattern in O(n + m) without stepping back in the text; the prefix function also finds a string's period. O(n + m) 2 problems