今天是地底世界重见光明的纪念日！
为了庆祝这历史性的一天，居民们在Undyne的带领下列队游行表演！
参与游行表演的居民们都要上场——所以队列中的人数一定是 。居民们可以在两种类型的旗子中任选一种来举着参加游行表演，这两种旗子不妨称之为类型a和类型b。Alphys为了让游行表演更好看一点，决定队伍里面不能出现aaa或者aba的旗子组合，现在Alphys想知道，对于有 位居民参与的游行表演，最终会有多少种不同的队列呢？（由于这个数可能会很大，请对 取模后输出）
不定组数据输入，保证输入组数不超过
每组数据输入一行 个正整数 ，，表示居民的数量和模数
不定组数据输出 每组数据输出一行 个整数，表示不同的队列种数
1 1000000007 3 1000000007
2 6
，
