yukicoder-579

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/579 No.579 3 x N グリッド上のサイクルのサイズ(hard)] ==

=== Description ===

{{{
#!html
<p>有下面一个$4$行$N+1$列的格点图。</p>

<img src="http://10.71.10.90/zimpha/images/yukicoder-579.png" />

<p>求图中所有简单环的长度之和$\bmod (10^9+7)$。</p>
}}}

=== Input ===

{{{
#!html
<p class="input">$N$</p>
<p>
$1 \leq N \leq 10^{18}$
</p>
}}}

=== Output ===

{{{
#!html
输出所有简单环的长度之和$\bmod (10^9+7)$。
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
1
</pre>
}}}
输出
{{{
#!html
<pre>
32
</pre>
}}}

{{{
#!html
<p>有$3$个长度为$4$的环，$2$个长度为$6$的环，$1$个长度为$8$的环，总和为$3\times 4 + 2 \times 6 + 1 \times 8 = 32$。</p>

<p>$N=2,\dots,10$的答案分别是$316, 2292, 14422, 84744, 479004, 2638328, 14258574, 75940592, 399782668$。</p>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
20
</pre>
}}}
输出
{{{
#!html
<pre>
424899366
</pre>
}}}

No.579 3 x N グリッド上のサイクルのサイズ(hard)

Description

有下面一个$4$行$N+1$列的格点图。

求图中所有简单环的长度之和$\bmod (10^9+7)$。

Input

$N$

$1 \leq N \leq 10^{18}$

Output

输出所有简单环的长度之和$\bmod (10^9+7)$。

Sample

Sample 1

输入

输出

有$3$个长度为$4$的环，$2$个长度为$6$的环，$1$个长度为$8$的环，总和为$3\times 4 + 2 \times 6 + 1 \times 8 = 32$。

$N=2,\dots,10$的答案分别是$316, 2292, 14422, 84744, 479004, 2638328, 14258574, 75940592, 399782668$。

Sample 2

输入

输出

424899366