cipari

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define MOD 1000000009

ll dp[100009];//the number of ways to construct this number

/*
0
1
10
11
100
101
110
111
1000
1001
*/

int main(){
    ios::sync_with_stdio(false);
    string s;
    cin >> s >> s;
    dp[0]=1;
    int l = 1;
    for(int i = 0;i<s.size();i++){
        dp[l]=dp[l-1];
        for(int j = 2;j<=3 and l-j>=0;j++){
            if(s[i-j+1]=='1')dp[l]+=dp[l-j];
        }
        if(l>=4){
            if(s[i]=='0' and s[i-1]=='0' and s[i-2]=='0' and s[i-3]=='1'){
                dp[l]+=dp[l-4];
            }
            if(s[i]=='1' and s[i-1]=='0' and s[i-2]=='0' and s[i-3]=='1'){
                dp[l]+=dp[l-4];
            }
        }
        dp[l]%=MOD;
        l++;
    }
    cout << dp[s.size()] << "\n";
    string ans;
    l=s.size()-1;
    while(l>=0){
        if(l>=3){
            if(s[l]=='1' and s[l-1]=='0' and s[l-2]=='0' and s[l-3]=='1'){
                l-=4;
                ans+='9';
                continue;
            }
            if(s[l]=='0' and s[l-1]=='0' and s[l-2]=='0' and s[l-3]=='1'){
                l-=4;
                ans+='8';
                continue;
            }
        }
        if(l>=2){
            if(s[l]=='1' and s[l-1] == '1' and s[l-2]=='1'){
                l-=3;
                ans+='7';
                continue;
            }
            if(s[l]=='0' and s[l-1]=='1' and s[l-2]=='1'){
                l-=3;
                ans+='6';
                continue;
            }
            if(s[l]=='1' and s[l-1]=='0' and s[l-2]=='1'){
                l-=3;
                ans +='5';
                continue;
            }
            if(s[l]=='0' and s[l-1]=='0' and s[l-2]=='1'){
                l-=3;
                ans+='4';
                continue;
            }
        }
        if(l>=1){
            if(s[l]=='1' and s[l-1]=='1'){
                l-=2;
                ans += '3';
                continue;
            }
            if(s[l]=='0' and s[l-1]=='1'){
                l-=2;
                ans += '2';
                continue;
            }
        }
        if(s[l]=='1'){
            l--;
            ans += '1';
            continue;
        }
        else{
            l--;
            ans += '0';
            continue;
        }
    }
    reverse(ans.begin(),ans.end());
    cout << ans;
    return 0;
}