假設 \(n\) 是 \(2\) 的冪次，也就是存在某個非負整數 \(k\) 使得 \(n = 2^k\)。將一個 \(n*n\) 的黑白影像以下列遞迴方式編碼： 如果每一格像素都是白色，我們用 0 來表示； 如果每一格像素都是黑色，我們用 1 來表示；否則，並非每一格像素都同色，先將影像均等劃分為四個邊長為 \(\frac{n}{2}\) 的小正方形後，然後表示如下：先寫下 2，之後依續接上左上、右上、左下、右下四塊的編碼。 輸入編碼字串 \(S\) 以及影像尺寸 \(n\)，請計算原始影像中有多少個像素是 \(1\)。

輸入格式

第一行是影像的編碼 \(S\)，字串長度小於 \(10^6\)。 第二行為正整數 \(n\)， \(1 \leq n \leq 1024\)，其中 \(n\) 必為2的冪次。

輸出格式

輸出有多少個像素是 \(1\)。

範例輸入

2020020100010
8

範例輸出

17