{"problem":{"name":"D. Уголки","description":{"content":"Петя с двумя друзьями писал контест. Но тут его сокомандники отказались писать задачу, потому что она сложная. Расстроенный Петя раскатал первого из друзей в полоску, состоящую из 2 на n одинаковых кв","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10144D"},"statements":[{"statement_type":"Markdown","content":"Петя с двумя друзьями писал контест. Но тут его сокомандники отказались писать задачу, потому что она сложная. Расстроенный Петя раскатал первого из друзей в полоску, состоящую из 2 на n одинаковых квадратных клеточек, а второго разрезал на k уголков по три клеточки каждый. Теперь он интересуется вопросом: а сколько способов разместить эти уголки на полоске так, чтобы они не пересекались (то есть, чтобы ни одна клетка полосы не была покрыта более чем одним уголком). Петя не может отличить один уголок от другого, так что расстановки, отличающиеся только порядком уголков следует считать одинаковыми. Так как число способов может быть большим, а Петя добрый мальчик, ответ нужно вывести по модулю 109 + 7.\n\nДва натуральных числа n и k через пробел, 1 ≤ n ≤ 5000, 1 ≤ k ≤ 109.\n\nВыведите единственное число – ответ на задачу.\n\n## Входные Данные\n\nДва натуральных числа n и k через пробел, 1 ≤ n ≤ 5000, 1 ≤ k ≤ 109.\n\n## Выходные Данные\n\nВыведите единственное число – ответ на задачу.\n\n## Примеры\n\nВходные данные2 1Выходные данные4Входные данные2 2Выходные данные0Входные данные3 2Выходные данные2Входные данные10 4Выходные данные5820\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ k \\in \\mathbb{Z} $, $ 1 \\leq k \\leq 10^9 $.  \nLet $ A = (A_1, A_2, \\dots) $ be an infinite sequence of integers satisfying the recurrence:  \n$$\nA_{n+1} = A_n \\quad \\text{for all } n \\geq 1, \\quad \\text{and} \\quad A_{k+1} = A_1.\n$$\n\n**Constraints**  \n1. $ A_{k+1} = A_1 $  \n2. All $ A_i \\in \\mathbb{Z} $  \n3. The sequence is constant: $ A_1 = A_2 = \\cdots = A_{k+1} = x $ for some $ x \\in \\mathbb{Z} $\n\n**Objective**  \nCount the number of integer values $ x \\in \\mathbb{Z} $ such that the condition $ A_{k+1} = A_1 = x $ is satisfied.  \n\nIf infinitely many such $ x $ exist, output $ -1 $.  \nOtherwise, output the count modulo $ 10^9 + 7 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10144D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}