Мирко и Славко играют в игру. Мирко ходит первым и выбирает непустое множество пар чисел от 1 до N (включительно). При этом числа в одной паре должны быть различны и взаимнопросты. Например, для N = 5 , Мирко может выбрать такое множество пар: {(1, 2), (3, 4), (2, 5), (3, 5)}.

Славко ходит вторым и его задача - найти разделяющий элемент для множества пар Мирко. Разделяющим элементом для множества пар называется такое число x из диапазона [2: N ] , что для каждой пары ( a , b ) из множества выполняется одно из двух условий:

1. a , b < x

2. a , b ≥ x

Например, множество пар {(1, 2), (3, 4)} имеет разделяющий элемент x = 3 .

Если разделяющий элемент существует, Славко обязательно его найдет, и тогда он выиграет. Мирко же выиграет, если Славко не сможет найти разделяющий элемент. Он просит вас помочь: определите, как много множеств пар, удовлетворяющих условию, он может выбрать, чтобы гарантированно выиграть. Так как это число может быть очень большим, выведите его по модулю 1 000 000 000.