Codeforces Round 167 (Div. 1) |
---|
Закончено |
Дима и Аня любят играть в разные игры. Сейчас Дима придумал новую игру, в которую хочет поиграть с Аней.
Дима пишет на листке n пар целых чисел (li, ri) (1 ≤ li < ri ≤ p). Далее игроки ходят по очереди. За один ход игрок может выполнить следующее действие:
Игрок, который не может сделать ход — проигрывает.
Конечно, Дима хочет, чтобы Аня, которая будет ходить первая, выиграла. Поэтому Дима должен выписать такие n пар целых чисел (li, ri) (1 ≤ li < ri ≤ p), чтобы при оптимальной игре обоих игроков выигрывал первый. Посчитайте, сколькими способами Дима может это сделать. Выведите остаток от деления ответа на число 1000000007 (109 + 7).
Два способа считаются различными, если различаются упорядоченные последовательности выписанных пар.
В первой строке даны два целых числа n, p (1 ≤ n ≤ 1000, 1 ≤ p ≤ 109). Числа разделены единичным пробелом.
В единственную строку выведите остаток от деления ответа на задачу на число 1000000007 (109 + 7).
2 2
0
4 4
520
100 1000
269568947
Название |
---|