```go
package main

import (
	"fmt"
	"math"
	"sort"
	"strconv"
)

type Element struct {
	val int64
	str string
}

var CTs map[int64]string

func add_CT(val int64, s string) {
	if val > 10000000000 {
		return
	}
	valStrLen := len(strconv.FormatInt(val, 10))
	if len(s) >= valStrLen {
		return
	}
	if existing, ok := CTs[val]; !ok || len(s) < len(existing) {
		CTs[val] = s
	}
}

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

	CTs = make(map[int64]string)
	var SCPs []Element

	for Y := 2; Y <= 34; Y++ {
		for X := int64(2); ; X++ {
			valFloat := math.Pow(float64(X), float64(Y))
			if valFloat > 10000000000.5 {
				break
			}

			exact := int64(1)
			for i := 0; i < Y; i++ {
				exact *= X
			}
			if exact > 10000000000 {
				break
			}

			s := strconv.FormatInt(X, 10) + "^" + strconv.Itoa(Y)
			valStrLen := len(strconv.FormatInt(exact, 10))
			if len(s) < valStrLen {
				SCPs = append(SCPs, Element{exact, s})
			}
		}
	}

	sort.Slice(SCPs, func(i, j int) bool {
		return SCPs[i].val < SCPs[j].val
	})

	for _, p := range SCPs {
		add_CT(p.val, p.str)
	}

	for i := 0; i < len(SCPs); i++ {
		for j := i; j < len(SCPs); j++ {
			if SCPs[i].val > 10000000000/SCPs[j].val {
				break
			}
			val := SCPs[i].val * SCPs[j].val
			add_CT(val, SCPs[i].str+"*"+SCPs[j].str)
			add_CT(val, SCPs[j].str+"*"+SCPs[i].str)
		}
	}

	for _, p := range SCPs {
		limit := 10000000000 / p.val
		if limit < 2 {
			continue
		}

		max_len := 10 - len(p.str) - 1
		if max_len < 1 {
			continue
		}

		max_N := int64(math.Pow(10, float64(max_len))) - 1
		if max_N > limit {
			max_N = limit
		}

		for N := int64(2); N <= max_N; N++ {
			val := N * p.val
			nStr := strconv.FormatInt(N, 10)
			add_CT(val, p.str+"*"+nStr)
			add_CT(val, nStr+"*"+p.str)
		}
	}

	best := strconv.FormatInt(n, 10)

	if s, ok := CTs[n]; ok {
		if len(s) < len(best) {
			best = s
		}
	}

	for ct_val, ct_str := range CTs {
		if ct_val >= n {
			continue
		}
		rem := n - ct_val
		remStr := strconv.FormatInt(rem, 10)

		cand1 := ct_str + "+" + remStr
		if len(cand1) < len(best) {
			best = cand1
		}
		cand2 := remStr + "+" + ct_str
		if len(cand2) < len(best) {
			best = cand2
		}

		if rem_str, ok := CTs[rem]; ok {
			cand3 := ct_str + "+" + rem_str
			if len(cand3) < len(best) {
				best = cand3
			}
		}
	}

	fmt.Println(best)
}
```