#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<=M;i++){ for(int j=0;j<=D;j++){ if(j-i>=0)dp[i][j]+=dp[i][j-i]+dp[i-1][j-i]; if(j-N-1>=0)dp[i][j]-=dp[i-1][j-N-1]; } } cout << dp[M][D] << endl; return 0; }