private int fx(String s, Map<String, Integer> cache) {
		if (cache.containsKey(s)) {
			return cache.get(s);
		}

		if (s.length() == 1) {
			cache.put(s, 1);
			return 1;
		}

		if (s.length() == 2) {
			int sn = Integer.valueOf(s);
			if (sn <= 26) {
				cache.put(s, 2);
				return 2;
			} else {
				cache.put(s, 1);
				return 1;
			}
		}

		int total = 0;
		for (int i = 1; i < s.length(); i++) {
			int lx = fx(s.substring(0, i), cache);
			int rx = fx(s.substring(i), cache);
			total += lx * rx;
		}
		cache.put(s, total);
		return total;
	}