Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Треугольник Штерна строится следующим образом.
`n`-я строка содержит `2^n-1` элементов
Обозначим значение `k`-го элемента в `n`-й строке как `S(n, k)`.
Будем считать, что `S(n, k) = 0` если `k = 0` или `k = 2^n`.
Тогда\
`S(1, 1) = 1`\
`S(n+1, 2*k) = S(n, k)` для `n >= 1`\
`S(n+1, 2*k+1) = S(n, k) + S(n, k+1)`.
Первые 6 строк треугольника Штерна выглядят так:
```text
1
1 1 1
1 1 2 1 2 1 1
1 1 2 1 3 2 3 1 3 2 3 1 2 1 1
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 4 3 5 2 5 3 4 1 3 2 3 1 2 1 1
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 2 7 5 8 3 7 4 5 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 4 3 5 2 5 3 4 1 3 2 3 1 2 1 1
```
При достаточно большом `n` `S(n+1,k)=S(n,k)`.
Рассмотрим предельную последовательность `B(k)=lim_{n->oo} S(n,k)`.
Можно доказать, что для любого рационального положительного числа `p/q`, где `gcd(p,q)=1`,
существует ровно одно `k`, такое что `p/q={B(k)}/{B(k+1)}`. Например, `3/5={B(10)}/{B(11)}`.
Напишите программу, которая находит заданное рациональное число в последовательности `B(k)`.
Первая строка ввода содержит два взаимно простых целых числа `p` и `q` (`1 <= p, q <= 200000`).
Вывести одно целое число -- номер элемента `k` по модулю `1 000 000 007`.
```sample Пример ввода 1
3 5
```
```sample Пример вывода 1
10
```
```sample Пример ввода 2
123 67
```
```sample Пример вывода 2
131197
```
Начало
Рабочее место участника
Модулярная арифметика