AGC003
A
Snuke有一个n天的旅行计划。第\(i\)天准备向\(A_i\)方向移动一个正数距离（\(A_i\in\{\textrm{N,S,W,E}\}\)。
问可不可能安排每天移动的距离，使得最后回到出发点。
如果N,S同时存在或同时不存在，W,E同时存在或同时不存在，就可以（显然
B
Snuke有一大堆卡，每张卡上有一个\(1\dots n\)的数字。
其中有\(A_i\)张卡上数字为\(i\)。Snuke每次可以选出两张数字差不超过1的卡并组成一组。
求最多组成多少组。
结论：若\(A_i\)中没有\(0\)，则答案为\(\lfloor\frac{\sum A_i}{2}\rfloor\)。
证明很显然。显然不可能凑出超过这么多组。但还要构造一个这么多组的方案：
把这\(\sum A_i\)张卡按数字从小到大排列，显然相邻两张卡数字差不超过\(1\)（因为\(A_i\not=0\)
然后把1,2张,3,4张\(\dots\)分成一组，就能得到答案。
至于有0怎么办呢？把数列从0处分开计算就好了。
C
Snuke有一个长度为\(n\)元素两两不同的序列\(a_1\dots a_n\)。他希望通过两个操作将这个序列升序排序：
- 选取\(i\)，并交换\(a_i,a_{i+1}\)
- 选取\(i\)，并交换\(a_i,a_{i+2}\)
求使用\(1\)的最少次数。
首先把序列离散化得到排列\(c_1\dots c_n\)。
那么要把\(c\)升序排序，\(c_i\)和\(i\)奇偶性不同的位置必须用1操作来修正，因为\(2\)不会改变\(c_i\)位置的奇偶性。
显然有多少个奇数在偶数位，就有多少个偶数在奇数位。所以只需要统计前者。
D
Snuke有\(n\)个整数\(s_1\dots s_n\)。Snuke希望选出尽量多的数，使得任意两个选出来的数乘积不能表示成\(x^3\)其中\(x\)是整数。\(n\le 10^5,s_i\le 10^{10}\)。
有一个很显然的思路：
把\(s_i\)中立方因子去掉，然后算出每个\(s_i\)要补成立方数需要乘的最小的数\(s'_i\)，显然如果\(s_i=s'_j\)，\(s_i,s_j\)就不能同时出现。
然后把\(s_i\)和\(s'_i\)放进一个map里面判断一下就可以了。
当然1要特别考虑。
但是质因数分解怎么办呢？
无脑Pollard_Rho就可以啦
首先分解掉\(\le 10^{\frac{10}{3}}\)的质因子，然后剩下的数一定不超过2个质因子了！不然肯定就超过了！
然后判断一下剩下的数是不是完全平方数。
如果\(s'_i\)特别大呢？
特别大显然就没用了，直接记为-1或其它数就好了。
E
有一个长度为\(n\)的序列\(1,2\dots n\)，现在要进行\(q\)个操作。
第\(i\)个操作给定一个数\(a_i\)，然后把原序列无限复制，取前\(a_i\)个得到新序列。
求最后\(1\dots n\)的个数。
首先把\(a_i\)(\(a_0=n\))存进单调栈，得到一个单调递增的数列\(s_1,s_2\dots s_m\)。
然后记\(f(m,w)\)表示第\(m\)个数列前\(w\)个元素得到的答案。
以及 答案可以用差分快速区间加法。
那么\(f(1,n)=\)前\(n\)个数各1次。\(f(m,w)=\lfloor\frac{w}{s_{m-1}}\rfloor f(m-1,s_{m-1})+f(m-1,{w\bmod s_{m-1}})\)
恭喜你得到了一个时间复杂度巨大的算法。
然后发现，\(f(m,s_m)\)这部分的计算可以先得到它对答案的系数然后统一计算。
然后我们就得到了一个\(O(q^2)\)的算法。
注意一个数\(w\)对很多数字取膜，有效的取膜次数不超过\(\log w\)。
所以每次可以二分出下一个取膜的位置。
时间复杂度就变成了优秀的\(O(q\log^2 s_m)\)了。
F
给定一个图形（\(W\times H\)的矩形，每个格子可以是黑或白。），定义它的k阶分形为：
0阶分形为一个黑格子。
\(k\)阶分形为\(k-1\)阶分形的基础上：
每个白格子变成了一个\(W\times H\)的全白矩形，每个黑格子变成了一个\(W\times H\)的给定图形。
当然也可以定义为在原图形的基础上，每个黑格子变成了一个k-1阶分形，白格子变成同样大的全白矩形。
已知原图形黑格子四联通，求它的\(k\)阶分形联通块的个数。
定义\(s\)是原图形黑格子个数。
若某一行最左和最右都是黑色，则称为左右连接。
若某一列最上和最下都是黑色，则称为上下连接。
若存在行左右连接，存在列上下连接，则整个图形联通，答案是1。
若都不存在，则答案为\(s^{k-1}\)（1阶分形是它自己）。
否则：
假设存在行左右连接（上下连接也一样），
把每个原图形视为一个点，显然上下两个点是不连通的，而左右的点形成了一条条横的链。
那么联通块个数就是点数-边数。
点数显然就是\(s^{k-1}\)，边数呢？
设\(e_k\)表示k阶分形的得到链的边数。\(a\)为左右连接的个数，\(b\)为横着连续两个都是黑格子的个数。
则\(e_2=b\)，\(e_n=se_{n-1}+a^{n-2}b\)。
首先显然n-1阶分形的边数*s都是，然后还有多的。
\(n\)阶分形这\(b\)个连续两个都是黑格子的格子对，每一对两边相接的地方对应到\(n-1\)都是\(a^{n-2}\)个1阶分形相接。
然后把\(e_n\)展开得到\(b\sum_{i=0}^{n-2}a^is^{n-2-i}\)，等比数列求和一波就可以了。
Code
A
/*
Author: CNYALI_LK
LANG: C++
PROG: a.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int c[256];
char s[2333];
int main(){
#ifdef cnyali_lk
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
read(s);
for(int i=0;s[i];++i)c[s[i]]=1;
write((c['N']==c['S'] && c['E']==c['W'])?"Yes\n":"No\n");
return 0;
}
B
/*
Author: CNYALI_LK
LANG: C++
PROG: b.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
signed main(){
#ifdef cnyali_lk
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
int n,s=0,t=0,x;
read(n);
for(int i=1;i<=n;++i){
read(x);
if(!x){s+=t>>1;t=0;}
else t+=x;
}
s+=t>>1;
write(s,'\n');
return 0;
}C
/*
Author: CNYALI_LK
LANG: C++
PROG: c.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int a[100005],b[100005],c[100005];
int main(){
#ifdef cnyali_lk
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
#endif
int n,ans=0;
read(n);
for(int i=1;i<=n;++i){read(a[i]);b[i]=i;}
sort(b+1,b+n+1,cmp_a<a>);
for(int i=1;i<=n;++i)c[b[i]]=i;
for(int i=1;i<=n;i+=2)if(!(c[i]&1))++ans;
write(ans,'\n');
return 0;
}
D
/*
Author: CNYALI_LK
LANG: C++
PROG: d.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
const int M=(int)1e10;
int a[100005];
ll u[100005],v[100005];
map<ll,ll> ump,vmp;
signed main(){
#ifdef cnyali_lk
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
#endif
int n,t;
read(n);
int qaq=0;
for(int i=1;i<=n;++i){
read(a[i]);
u[i]=v[i]=1;
for(int j=2;j*j*j<=M;++j){
t=0;
while(!(a[i]%j)){
a[i]/=j;
++t;
}
t%=3;
if(t==1){u[i]*=j;v[i]*=j*j;}
if(t==2){u[i]*=j*j;v[i]*=j;}
}
t=(ll)(sqrt(a[i])+0.5);
if(t*t==a[i]){u[i]*=a[i];v[i]*=t;}
else {u[i]*=a[i];ll ov=v[i];v[i]*=a[i]*a[i];if(v[i]/a[i]/a[i]!=ov)v[i]=-1;}
if(u[i]==1){
qaq=1;
continue;
}
++vmp[v[i]];
++ump[u[i]];
// write(u[i],' ',v[i],'\n');
}
int ans=0,ans1=0;
for(auto i:ump){
if(vmp[i.x])ans1+=max(i.y,vmp[i.x]);
else ans+=i.y;
}
write(ans+(ans1>>1)+qaq,'\n');
return 0;
}
E
/*
Author: CNYALI_LK
LANG: C++
PROG: e.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
ll w[100005],t,a[100005],pw[100005];
void Work(ll t,ll x,ll pm){
if(t==1){
a[1]+=pm;
a[x+1]-=pm;
return;
}
pw[t-1]+=pm*(x/w[t-1]);
x%=w[t-1];
if(!x)return;
ll r=upper_bound(w+1,w+t+1,x)-w;
Work(r,x,pm);
}
int main(){
#ifdef cnyali_lk
freopen("e.in","r",stdin);
freopen("e.out","w",stdout);
#endif
ll n,q,xw;
read(n,q);
w[t=1]=n;
for(ll i=1;i<=q;++i){
read(xw);
while(t && w[t]>=xw)--t;
w[++t]=xw;
}
pw[t]=1;
for(ll i=t;i;--i){
if(pw[i])Work(i,w[i],pw[i]);
}
for(ll i=1;i<=n;++i)write(a[i]+=a[i-1],'\n');
return 0;
}F
/*
Author: QAQ-Automaton
LANG: C++
PROG: f.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
char s[1005][1005];
ll hs,ls,v,a,b;
ll n,m,k;
const ll p=1000000007;
ll fpm(ll a,ll b){
return b?b&1?fpm(a,b-1)*a%p:sqr(fpm(a,b>>1))%p:1;
}
ll calc(ll n){
ll s=v*fpm(a,p-2)%p;
return b*fpm(a,n)%p*(fpm(s,n+1)-1)%p*fpm(s-1,p-2)%p;
}
int main(){
#ifdef QAQAutoMaton
freopen("f.in","r",stdin);
freopen("f.out","w",stdout);
#endif
scanf("%lld%lld%lld\n",&n,&m,&k);
if(k<=1){write("1\n");return 0;}
for(ll i=1;i<=n;++i){
scanf("%s",s[i]+1);
if(s[i][1]=='#' && s[i][m]=='#')++hs;
for(ll j=1;j<=m;++j)v+=s[i][j]=='#';
}
for(ll i=1;i<=m;++i)
if(s[1][i]=='#' && s[n][i]=='#')++ls;
ll f=fpm(v,k-1);
if(!hs && !ls)write(f,'\n');
else if(hs && ls)write("1\n");
else{
a=hs+ls;
if(hs){
for(ll i=1;i<=n;++i)for(ll j=1;j<m;++j)if(s[i][j]=='#' && s[i][j+1]=='#')++b;
}
else{
for(ll i=1;i<n;++i)for(ll j=1;j<=m;++j)if(s[i][j]=='#' && s[i+1][j]=='#')++b;
}
write((f+p-calc(k-2))%p,'\n');
}
return 0;
}