注意

言語によっては実行時間制限キツイっぽいです。C++/Java/C#等の速い言語で解くことを推奨します。

参考

• C++は特に意識して頑張らなくても 442 ms で通ってます。
• Java素人のwriterがJavaで頑張ってみて 1118 ms で通ってます。
• C#素人のwriterがC#で頑張ってみて1～2ケースTLEだったので、camypaperさんの入出力メソッドをコピペしたら 1747 ms で通りました。
• python素人のwriterがpypyで頑張ってみてもダメでした(TLE)。 → もう少し工夫したら1.2secぐらいで通りました。 python3で通してる方も何人かいます。

問題文

ある芸人のモノマネをする芸人が現れました。
彼は「3の倍数 もしくは 3のつく数」のとき「アホ」になり、「$P$の倍数($P$は 8, 80, 800 のいずれか)」のとき「恥じらい」を見せます。
$A$ 以上 $B$ 以下の整数のうち、「アホ」になりかつ「恥じらい」を見せない数がいくつあるかを $10^9+7$ で割った時の余りで求めてください。

入力

A B P

入力はすべて整数で与えられる。
$1 \leq A \leq B \leq 10^{200000} = 10^{2 \times 10^5}$
$P$は 8, 80, 800 のいずれか

出力

$A$ 以上 $B$ 以下の整数のうち、「アホ」になりかつ「恥じらい」を見せない数がいくつあるかを $10^9+7$ で割った時の余りで出力してください。

サンプル

1 100 8

40

114 514 80

235

1234 567890 800

384205