Codeforces Round #157 (ディビジョン 2)D (デジタル DP + 組み合わせの数)_html/css_WEB-ITnose

D. 小さなゾウと選挙

テストごとの制限時間

2 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

があります最近動物園で選挙がありました。全体として、主要な政党は 7 つありました。そのうちの 1 つはリトル エレファント政党で、他の 6 つの政党はそれほどキャッチーな名前ではありません。

政党は投票用紙に含まれる政党の数が非常に重要であると考えています。全体として、考えられる数は m 個あります: 1、?2、?...、?m。これら 7 つの政党のそれぞれに、何らかの方法で正確に 1 つの番号が割り当てられることになります。その際、2 つの異なる政党が同じ番号を受け取ることはできません。

リトル エレファント政党の党員は、幸運の数字 4 と 7 を信じています。彼らは評価したいと考えています。選挙での彼らのチャンス。そのためには、小象政党の投票番号の幸運の数字の数が、他の 6 つの政党の投票番号の幸運の数字の合計より厳密に大きくなるような、正しい割り当てがいくつあるかを調べる必要があります。

リトルエレファント政党を手伝って、この数字を計算してください。答えはかなり大きくなる可能性があるため、1000000007 (109?+?7) で割った余りを出力します。

入力

1 行には 1 つの正の整数 m (7?≤?m?≤?109) が含まれます。 ?投票用紙に含まれる数字の数。

出力

1 行に 1 つの整数を出力します。問題の答え、モジュロ 1000000007 (109?+?7)。

サンプル テスト

入力

出力

入力

出力

1440

题意：RT

思路：首先要预处処理出力4 または 7 に含まれる数字はどのくらい、dp[i] は i に含まれる 4 または 7 の数字を示します、dfs递推求解即可

有了これdp数组就開始可能，如果小象政治党选了含i个4または7的番号，要旨dp[i]

次に、次の 6 つのパーティー選択番号です。必要な 4 と 7 の数が少ないです。これは、バックパックの解決であり、感情的な目も問題ありません~