Two cases: *t* = 10 and *t* ≠ 10.

If *t* = 10 then there are two cases again :). If *n* = 1 then answer is - 1 (because there is not any digit divisible by *t*). If *n* > 1, then answer, for example, is '1111...110' (contains *n* - 1 ones).

If *t* < 10 then answer, for example, is 'tttttttt' (it, obviously, divisible by *t*).

The number of ways to choose *a*_{i} (without any conditions) — 3^{3n}. Let *A* be the number of ways to choose *a*_{i} with condition that in every triangle gnomes have 6 coins. Then answer is 3^{3n} - *A*.

Note that we can separate all gnomes on n independent triangles (*i*-th triangle contains of *a*_{i}, *a*_{i + n}, *a*_{i + 2n}, *i* < *n*). So we can count answer for one triangle and then multiply the results. To count answer for one triangle, we can note that there are 7 ways to choose gnomes with 6 coins (all permutations 1, 2, 3 and 2, 2, 2).

So answer is — 3^{3n} - 7^{n}. We count it in *O*(*n*).

Let's find a string that will be equal to *s*1 in *k* = *n* - *t* positions and equal to *s*2 in *k* = *n* - *t* positions. Let's denote *q* = quantity of *i* that *s*1_{i} = *s*2_{i}. If *k* ≤ *q*, then let's take *k* positions such that *s*1_{pos} = *s*2_{pos} and put in answer the same symbols. Then put in other *n* - *k* positions symbols, which are not equal to corresponding in *s*1 and *s*2 (we can do it, because we have 26 letters).

Now *k* > *q*. So, if there is an answer, where exists *pos* such that *s*1_{pos} = *s*2_{pos}, *s*1_{pos} ≠ *ans*_{pos}, let's denote *ans*_{i} = *s*1_{i}, and then in any position such that *s*1_{i} ≠ *s*2_{i} = *ans*_{i} and *s*1_{i} = *ans*_{i} (and in the same position in *s*2) we will choose *a*_{i}, such that *a*_{i} ≠ *s*1_{i} and *a*_{i} ≠ *s*2_{i} (we can do it because *k* > *q*). So, for every position from *q* we can put symbols, equal to corresponding symbols in *s*1 and *s*2. Now we have strings *s*1, *s*2 of length *n* - *q* (such that *s*1_{i} ≠ *s*2_{i} for every i) and we should find string *ans* such that *f*(*ans*, *s*1) = *f*(*ans*, *s*2). We know that *s*1_{i} ≠ *s*2_{i}, so *ans*_{i} may be equal to corresponding in *s*1 or to corresponding in *s*2 or not equal to *s*1_{i} and to *s*2_{i}. So, we need, at least, 2(*k* - *q*) symbols in answer to make *f*(*s*1, *ans*) = *k* - *q* and *f*(*s*2, *ans*) = *k* - *q*. Consequently, if *n* - *q* < 2(*k* - *q*), the answer is - 1, and else just put first *k* - *q* symbols in answer from *s*1, next *k* - *q* symbols from *s*2, and others won't be equal to corresponding in *s*1 and *s*2.

Solution works in *O*(*n*).

There is a fact that the distance between adjacent prime numbers isn't big. For *n* = 10^{9} maximal distanse is 282. So let's find maximal prime *p*, such that *p* < *n* - 1 (we can just decrease n while it's not prime(we can check it in )). We know that *n* - *p* < 300. Now we have even (because *n* and *p* are odd) number *n* - *p* and we should divide it into a sum of two primes. As *n* - *p* < 300, we can just iterate over small primes *P* and check if *P* is prime and *n* - *p* - *P* is prime. You can check that there is a solution for all even numbers less than 300 by bruteforce.

We can consider that we pay 2|*i* - *j*| coins for swap (we can divide answer in the end). Then we can consider that we pay |*i* - *j*| coins for moving *p*_{i} and |*i* - *j*| for moving *p*_{j}. So, if *x* was on position *i* and then came to position *j*, then we will pay at least |*i* - *j*| coins. Then the answer is at least (*pp* — position *k* in permutation *p*, and *ps* — position *k* in permutation *s*). Let's prove that this is the answer by showing the algorithm of making swaps.

Let's consider that permutation *s* is sorted (our task is equal to it). Then we will put numbers from *n* to 1 on their positions.

How we can put *n* on its position? Denote *p*_{pos} = *n*. Let's prove that there exists a position *pos*2 such that *pos* < *pos*2 and *p*_{pos2} ≤ *pos*(then we will swap *p*_{pos2} with *n* (and both numbers will move to their final positions and *n* will move to the right, so we can repeat this process until *n* returns to its position)). We can note that there are only *n* - *pos* positions that are bigger than *pos*. And how many numbers on these positions can be bigger than *pos*? We can say that answer is *n* - *pos*, but it's incorrect, because *n* is bigger than *pos*, but *pos*_{n} ≤ *pos*. Now we can use Pigeonhole principle and say that position *x*, such that *x* > *pos* and *p*_{x} ≤ *pos* exists.

But now our algorithm is *O*(*n*^{3}). How we can put *n* in its position in *O*(*n*) operations? Let's move the pointer to the right while number is bigger than *pos*. Then swap *n* with found number. After we can move pointer from new *n*'s position, so pointer always moves to the right and will not do more then *n* steps.