```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

const Base1 int64 = 313
const Mod1 int64 = 1000000007
const Base2 int64 = 317
const Mod2 int64 = 1000000009

type Hash struct {
	h1, h2 int64
}

var p_pow []Hash

func init_hash(n int) {
	p_pow = make([]Hash, n+1)
	p_pow[0] = Hash{1, 1}
	for i := 1; i <= n; i++ {
		p_pow[i].h1 = (p_pow[i-1].h1 * Base1) % Mod1
		p_pow[i].h2 = (p_pow[i-1].h2 * Base2) % Mod2
	}
}

func build_hash(s string) []Hash {
	n := len(s)
	h := make([]Hash, n+1)
	for i := 0; i < n; i++ {
		h[i+1].h1 = (h[i].h1*Base1 + int64(s[i])) % Mod1
		h[i+1].h2 = (h[i].h2*Base2 + int64(s[i])) % Mod2
	}
	return h
}

func get_hash(h []Hash, p []Hash, l, r int) Hash {
	len := r - l + 1
	v1 := (h[r+1].h1 - h[l].h1*p[len].h1) % Mod1
	if v1 < 0 {
		v1 += Mod1
	}
	v2 := (h[r+1].h2 - h[l].h2*p[len].h2) % Mod2
	if v2 < 0 {
		v2 += Mod2
	}
	return Hash{v1, v2}
}

func get_lce(hash_s, hash_rev []Hash, p_pow []Hash, L2, R2, n int) int {
	low := 0
	high := min(L2+1, n-R2)
	ans := 0
	for low <= high {
		mid := (low + high) / 2
		if mid == 0 {
			ans = 0
			low = mid + 1
			continue
		}
		h_rev := get_hash(hash_rev, p_pow, n-1-L2, n-1-L2+mid-1)
		h_fwd := get_hash(hash_s, p_pow, R2, R2+mid-1)
		if h_rev == h_fwd {
			ans = mid
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 1024*1024), 10*1024*1024)
	scanner.Split(bufio.ScanWords)

	if !scanner.Scan() {
		return
	}
	if !scanner.Scan() {
		return
	}
	s := scanner.Text()
	n := len(s)

	if n == 0 {
		return
	}

	rev_s_bytes := make([]byte, n)
	for i := 0; i < n; i++ {
		rev_s_bytes[i] = s[n-1-i]
	}
	rev_s := string(rev_s_bytes)

	init_hash(n)
	hash_s := build_hash(s)
	hash_rev := build_hash(rev_s)

	d1 := make([]int, n)
	for i, l, r := 0, 0, -1; i < n; i++ {
		k := 1
		if i <= r {
			k = min(d1[l+r-i], r-i+1)
		}
		for i-k >= 0 && i+k < n && s[i-k] == s[i+k] {
			k++
		}
		d1[i] = k
		if i+k-1 > r {
			l, r = i-k+1, i+k-1
		}
	}

	d2 := make([]int, n)
	for i, l, r := 0, 0, -1; i < n; i++ {
		k := 0
		if i <= r {
			k = min(d2[l+r-i+1], r-i+1)
		}
		for i-k-1 >= 0 && i+k < n && s[i-k-1] == s[i+k] {
			k++
		}
		d2[i] = k
		if i+k-1 > r {
			l, r = i-k, i+k-1
		}
	}

	rad := make([]int, 2*n-1)
	for i := 0; i < n; i++ {
		rad[2*i] = d1[i]
		if i < n-1 {
			rad[2*i+1] = d2[i+1]
		}
	}

	diff_left := make([]int64, n+1)
	diff_right := make([]int64, n+1)

	for C := 0; C <= 2*n-2; C++ {
		L_base := C / 2
		R_base := (C + 1) / 2
		r := rad[C]
		if r > 0 {
			diff_left[L_base-r+1]++
			diff_left[L_base+1]--

			diff_right[R_base]++
			diff_right[R_base+r]--
		}
	}

	left_count := make([]int64, n)
	right_count := make([]int64, n)
	var cur_l int64 = 0
	var cur_r int64 = 0
	var total_palindromes int64 = 0

	for i := 0; i < n; i++ {
		cur_l += diff_left[i]
		left_count[i] = cur_l
		total_palindromes += cur_l

		cur_r += diff_right[i]
		right_count[i] = cur_r
	}

	pref_right := make([]int64, n)
	pref_right[0] = right_count[0]
	for i := 1; i < n; i++ {
		pref_right[i] = pref_right[i-1] + right_count[i]
	}

	suff_left := make([]int64, n)
	suff_left[n-1] = left_count[n-1]
	for i := n - 2; i >= 0; i-- {
		suff_left[i] = suff_left[i+1] + left_count[i]
	}

	covering := make([]int64, n)
	for i := 0; i < n; i++ {
		c := total_palindromes
		if i > 0 {
			c -= pref_right[i-1]
		}
		if i < n-1 {
			c -= suff_left[i+1]
		}
		covering[i] = c
	}

	Loss := make([]int64, n)
	for i := 0; i < n; i++ {
		Loss[i] = covering[i] - int64(d1[i])
	}

	Gain := make([][26]int64, n)
	for C := 0; C <= 2*n-2; C++ {
		L_base := C / 2
		R_base := (C + 1) / 2
		r := rad[C]

		L1 := L_base - r
		R1 := R_base + r

		if L1 < 0 || R1 >= n {
			continue
		}

		L2 := L1 - 1
		R2 := R1 + 1

		ext := 0
		if L2 >= 0 && R2 < n {
			ext = get_lce(hash_s, hash_rev, p_pow, L2, R2, n)
		}

		count := int64(ext + 1)
		Gain[L1][s[R1]-'a'] += count
		Gain[R1][s[L1]-'a'] += count
	}

	var max_delta int64 = 0
	for i := 0; i < n; i++ {
		for c := 0; c < 26; c++ {
			if byte(c+'a') == s[i] {
				continue
			}
			delta := Gain[i][c] - Loss[i]
			if delta > max_delta {
				max_delta = delta
			}
		}
	}

	best_type1_i, best_type1_c := int(1e9), byte('z'+1)
	best_type2_i, best_type2_c := -1, byte('z'+1)

	for i := 0; i < n; i++ {
		for c := 0; c < 26; c++ {
			if byte(c+'a') == s[i] {
				continue
			}
			delta := Gain[i][c] - Loss[i]
			if delta == max_delta {
				char_c := byte(c + 'a')
				if char_c < s[i] {
					if i < best_type1_i {
						best_type1_i = i
						best_type1_c = char_c
					} else if i == best_type1_i && char_c < best_type1_c {
						best_type1_c = char_c
					}
				} else {
					if i > best_type2_i {
						best_type2_i = i
						best_type2_c = char_c
					} else if i == best_type2_i && char_c < best_type2_c {
						best_type2_c = char_c
					}
				}
			}
		}
	}

	fmt.Println(total_palindromes + max_delta)
	if best_type1_i != int(1e9) {
		out := []byte(s)
		out[best_type1_i] = best_type1_c
		fmt.Println(string(out))
	} else if max_delta == 0 {
		fmt.Println(s)
	} else {
		out := []byte(s)
		out[best_type2_i] = best_type2_c
		fmt.Println(string(out))
	}
}
```