레이팅 미적용Nick has always struggled with maintaining habits. The problem is that he just can't stop maintaining them. If Nick does something \(K\) times in a row, he has to keep doing it forever.
Luckily, he has started visiting Dr Patternson, an expert in PBT (Pattern Breaking Therapy). The principle of PBT is simple: Nick will visit Dr Patternson every day, and if he has done the same thing \(K\) times in a row on a specific visit, the doctor will charge him money. This will motivate Nick to not continue this habit.
PBT has worked out great for Nick, as he has now successfully quit all his habits. Except for one, the habit of visiting Dr Patternson. The frequent visits are starting to take a toll on Nick's economy, so your task is to calculate how many times he has to pay the doctor for the next \(N\) days.
Formally, let \(s = s_1s_2s_3\dots s_N\) be a string consisting of zeroes and ones. A one means that Nick has to pay the doctor on the \(i\)th day. This string is generated one character at a time, in the following way:
- \(s_i = 0\) if \(i \leq K\).
- If \(i > K\), then \(s_i = 1\) if the previous characters contains a pattern that repeats \(K\) times. More specifically, let \(s' = s_1s_2\dots s_{i-1}\). If there is a nonempty string \(t\) such that the last \(|t|\cdot K\) characters of \(s'\) can be written as \(t+t+\dots + t\), then \(s_i = 1\). Otherwise \(s_i = 0\).
You are given the numbers \(N\) and \(K\), and your task is to calculate the number of ones in the string \(s\).
The picture represents Sample 1. An angry face means that Nick had to pay on the corresponding day.
The input consists of one line with the integers \(N\) and \(K\) (\(1 \leq N \leq 10^9\), \(2 \leq K \leq 10^9\)).
Print one integer, the number of ones in the string \(s\).
7 2
3
99 5
19