显然的，先将原数变为四进制的数。
由于算的是进位/不进位的代价最小值和方案数，容易想到 dp。
这里假定该四进制数是从高位到低位的，顺序显然是由低位到高位。
令 \(f_{i,0/1}\) 表示第 \(i\) 位进 / 不进位的最小代价，\(g_{i,0/1}\) 表示的是最小代价下的方案数。
转移是简单的，对当前位的值分讨一下即可。
时空复杂度线性。
代码：
const int N=1e3+10,mod=1e9;
int n,cnt;
int a[N<<2],b[N],temp[N];
int f[N<<2][2],g[N<<2][2];
string s;
int main(){
cin>>s;
int n=s.size();
s=" "+s;
int len=n;
for(int i=1;i<=len;i++)
b[i]=s[i]-'0';
while(1){
for(int i=1;i<=len;i++)
temp[i]=b[i];
int now=0,lt=0;
for(int i=1;i<=len;i++){
now=now*10+temp[i];
if(lt||now>=4)
b[++lt]=now/4;
now%=4;
}
a[++cnt]=now;
len=lt;
if(!len)
break;
}
reverse(a+1,a+cnt+1);
f[cnt][0]=a[cnt],f[cnt][1]=4-a[cnt];
g[cnt][0]=g[cnt][1]=1;
for(int i=cnt-1;i;i--){
if(a[i]==3){
f[i][0]=a[i]+f[i+1][0];
g[i][0]=g[i+1][0];
if(f[i+1][0]+1<=f[i+1][1]){
f[i][1]=f[i+1][0]+1;
g[i][1]=g[i+1][0];
}
if(f[i+1][0]+1>=f[i+1][1]){
f[i][1]=f[i+1][1];
g[i][1]=(g[i][1]+g[i+1][1])%mod;
}
}else{
if(f[i+1][1]+1<=f[i+1][0]){
f[i][0]=a[i]+f[i+1][1]+1;
g[i][0]=g[i+1][1];
}
if(f[i+1][1]+1>=f[i+1][0]){
f[i][0]=a[i]+f[i+1][0];
g[i][0]=(g[i][0]+g[i+1][0])%mod;
}
if(f[i+1][0]+4-a[i]<=f[i+1][1]+3-a[i]){
f[i][1]=f[i+1][0]+4-a[i];
g[i][1]=g[i+1][0];
}
if(f[i+1][0]+4-a[i]>=f[i+1][1]+3-a[i]){
f[i][1]=f[i+1][1]+3-a[i];
g[i][1]=(g[i][1]+g[i+1][1])%mod;
}
}
}
if(f[1][0]<f[1][1]+1)
cout<<g[1][0]<<endl;
else if(f[1][0]>f[1][1]+1)
cout<<g[1][1]<<endl;
else
cout<<(g[1][0]+g[1][1])%mod<<endl;
return 0;
}