D-小红开灯（三，hard）_牛客周赛 Round 89

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

（本题和easy版本的唯一区别是，本题小红可以改变任意 $k$ 盏灯的状态）
有 $n$ 盏灯排成一列，初始为全部都是“开启”状态。

小红每次操作可以改变任意 $k$ 盏灯的状态（开启变关闭，关闭变开启），她想知道，进行任意次操作后，可以形成多少种不同的灯的状态？由于答案可能过大，请对 $10^9+7$ 取模。

输入描述:

两个正整数，用空格隔开。

输出描述:

一个整数，代表最终状态数对取模的答案。

示例1

输入

复制

3 2

输出

复制

说明

可以形成"111"、"100"、"010"、"001"这四种状态。