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 i := 0; i < size; i++ {
		for k := 0; k < size; k++ {
			if A[i][k] == 0 {
				continue
			}
			for j := 0; j < size; j++ {
				C[i][j] += A[i][k] * B[k][j]
			}
		}
	}
	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 := make([][]int64, size)
	for i := range base {
		base[i] = make([]int64, size)
		copy(base[i], A[i])
	}
	for p > 0 {
		if p%2 == 1 {
			res = multiply(res, base)
		}
		base = multiply(base, base)
		p /= 2
	}
	return res
}

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

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

	for i := 0; i < m; i++ {
		for _, c := range []byte{'0', '1'} {
			temp := s[:i] + string(c)
			nxt := 0
			for j := len(temp); j >= 1; j-- {
				if s[:j] == temp[len(temp)-j:] {
					nxt = j
					break
				}
			}
			if nxt < m {
				M[i][nxt]++
			}
		}
	}

	res := power(M, n)
	var avoid int64 = 0
	for i := 0; i < m; i++ {
		avoid += res[i][i]
	}

	total := int64(1) << n
	fmt.Println(total - avoid)
}