描述

河蟹是一个打字员，他经常要重复将某个字串复制很多遍。但他又很笨，每次打完初始字串后都只会按Ctrl+A、Ctrl+C，再按N下Ctrl+V将其复制到N遍（使屏幕上出现N个初始字串），于是经常弄得他满头是汗。为了减轻他的工作量，他委托你编写一个程序，求：从一个初始字串开始，按住Ctrl不放，最少要按多少个键（A或C或V）才能将字串复制到N遍呢？并且请你算出在按键最少的情况下有多少种不同按法。

格式

输入格式

只有一行，即数N。

输出格式

包含两行，第一行是最少按键数，第二行是不同的按法总数。

样例1

样例输入1

15

样例输出1

12
2

限制

因数据点而不同，最多5s，最少1s。

提示

[样例解释]
两种按法可以得到15个初始字串：
Ctrl+A+C+V+V+V+A+C+V+V+V+V+V
Ctrl+A+C+V+V+V+V+V+A+C+V+V+V
[题目提示]
沙茶题，别想繁了！！！
[数据规模]
对于20%的数据，N<=10000（即ZeroJudge原题数据范围）
对于50%的数据，N<=10^8
对于100%的数据，2<=N<=10^16

来源

ZeroJudge d304，有较大改动，组合键的功能更接近真实，数据范围也扩大了很多。当然，由于数据范围扩大了，也就不能输出方案了。