首页 > 试题广场 >

二分图染色(弱化版)

[编程题]二分图染色(弱化版)
  • 热度指数:37 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 512M,其他语言1024M
  • 算法知识视频讲解
给定一个完全二分图,图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿色,并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。
计算所有满足条件的染色的方案数,并对10^9+7取模。
(ps:本题数据量与实际比赛中数据量相比,少了一些)

输入描述:
二分图单边的顶点数目n(n ≤ 10^7)


输出描述:
输出一个整数,即所求的答案。
示例1

输入

2

输出

35

这道题你会答吗?花几分钟告诉大家答案吧!