Байтляндия пытается отправить космическую миссию на планету Bit-X. Их задачу усложняет то, что орбита планеты регулярно патрулируется Капитаном Битониксом, возглавляющим космические подразделения планеты Bit-X.

Вокруг Bit-X есть n станций пронумерованных по часовой стрелке от 1 до n. Станции равномерно расположены по круговой орбите, то есть станции с номерами i и i + 1 (1 ≤ i < n), а также станции с номерами 1 и n, являются соседними. Расстояние между любой парой соседних станций равняется m космическим милям. Патрулирование Капитана Битоникса заключается в том, что от запрыгивает в свою ракету на одной из станций и летает по кругу, пролетая по меньшей мере одну космическую милю перед тем, как приземлится на некоторой станции (возможно, той, с которой он взлетал).

Ракета Битоникса движется на энергии, получаемой от сжигания баков с топливом. После того, как Битоникс использует x-литровый бак с топливом и выбирает направление (по или против часовой стрелки), ракета пролетает ровно x космических миль по круговой орбите в выбранном направлении. Обратите внимание, что у ракеты нет тормозов; ракета не может остановиться, пока не опустошится бак с топливом.

Например, предположим, что n = 3, m = 60, а у Битоникса есть баки с топливом на 10, 60, 90 и 100 литров. Если Битоникс стартует со станции номер 1 и использует 100-литровый бак, чтобы лететь по часовой стрелке, затем использует 90-литровый бак, чтобы лететь по часовой стрелке, а затем использует 10-литровый бак, чтобы лететь против часовой стрелки, то он приземлится на станции номер 1, совершив корректный патруль. Обратите внимание, что Битоникс не обязан использовать все доступные баки с топливом. В данном примере Битоникс также может просто использовать 60-литровый бак, чтобы долететь до станции 2 или 3.

Однако, если бы n равнялось 3, m равнялось бы 60, а Битониксу были доступны только один бак на 10 литров и один бак на 100 литров, то он никак не смог бы совершить корректный патруль (он бы не смог приземлиться ровно на странции).

Космическое агентство Байтляндии хочет уничтожить некоторые топливные баки Капитана Битоникса таким образом, чтобы он не мог совершить ни одного корректного патруля. Сколькими способами можно уничтожить некоторое подмножество топливных баков Капитана Битоникса таким образом, чтобы он не мог совершить ни одного корректного патруля? Найдите описанное количество способов и выведите остаток от его деления на 1000000007 (10⁹ + 7).