测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A5988. 「美团 CodeM 初赛 Round A」二分图染色

编程题 普及+/提高
知识点

题目描述

给定一个完全二分图,图的左右两边的顶点数目相同。我们要把图中的每条边染成红色、蓝色、或者绿色,并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。计算所有满足条件的染色的方案数,并对 $10^{9}+7$ 取模。

输入格式

二分图单边的顶点数目 $n$。

输出格式

输出一个整数,即所求的答案。

输入输出样例

输入 #1
2
输出 #1
35

说明/提示

$n\leq10^7$
上一题 去做题 下一题