```go
package main

import (
	"fmt"
)

func multiply(A, B [][]int64) [][]int64 {
	size := len(A)
	C := make([][]int64, size)
	for i := range C {
		C[i] = make([]int64, size)
		for j := 0; j < size; j++ {
			var sum int64 = 0
			for k := 0; k < size; k++ {
				sum += A[i][k] * B[k][j]
			}
			C[i][j] = sum
		}
	}
	return C
}

func power(A [][]int64, p int) [][]int64 {
	size := len(A)
	res := make([][]int64, size)
	for i := range res {
		res[i] = make([]int64, size)
		res[i][i] = 1
	}
	base := A
	for p > 0 {
		if p%2 == 1 {
			res = multiply(res, base)
		}
		base = multiply(base, base)
		p /= 2
	}
	return res
}

func main() {
	var n int
	var s string
	if _, err := fmt.Scan(&n, &s); err != nil {
		return
	}

	m := len(s)
	A := make([][]int64, m)
	for i := range A {
		A[i] = make([]int64, m)
	}

	for i := 0; i < m; i++ {
		for c := 0; c <= 1; c++ {
			char := byte('0' + c)
			P := s[:i] + string(char)

			nextState := 0
			for k := len(P); k >= 1; k-- {
				if k <= m {
					if s[:k] == P[len(P)-k:] {
						nextState = k
						break
					}
				}
			}

			if nextState < m {
				A[i][nextState]++
			}
		}
	}

	An := power(A, n)
	var trace int64 = 0
	for i := 0; i < m; i++ {
		trace += An[i][i]
	}

	var total int64 = int64(1) << n
	ans := total - trace
	fmt.Println(ans)
}
```