#include #define rep(i,n) for(int i=0;i> S; int N=S.size(); assert(1<=N&&N<=60); int M=0; int D=0; rep(i,N){ assert(S[i]=='1'||S[i]=='0'); if(S[i]=='1'){ M++; D+=(i+1); } } ll dp[M+1][D+1]={}; dp[0][0]=1; for(int i=1;i<=N;i++){ ll ndp[M+1][D+1]={}; for(int j=0;j<=M;j++){ for(int k=0;k<=D;k++){ ndp[j][k]+=dp[j][k]; if(j>0&&k-i>=0){ ndp[j][k]+=dp[j-1][k-i]; } } } for(int j=0;j<=M;j++){ for(int k=0;k<=D;k++){ dp[j][k]=ndp[j][k]; } } } cout << dp[M][D] << endl; return 0; }